Verifique si alguna permutación de array contiene la suma de cada par adyacente que no es divisible por 3

Dada una array arr[] que consta de N enteros, la tarea es verificar si existe alguna permutación de los elementos de la array donde la suma de cada par de elementos adyacentes no es divisible por 3 . Si es posible, imprima “ Sí” . De lo contrario, escriba “ No” .

Ejemplos:

Entrada: arr[] = {1, 2, 3, 3}
Salida: Sí
Explicación:
Dado que existe al menos 1 combinación {3, 2, 3, 1} donde la suma de todos los pares adyacentes no es divisible por 3.

Entrada: arr[] = {3, 6, 1, 9}
Salida: No

Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones de la array dada y verificar si existe una disposición en la que la suma de dos elementos adyacentes no sea divisible por 3 . Si se determina que es cierto, imprima » Sí» . De lo contrario, escriba “ No” .

Complejidad temporal: O(N!)
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar que los únicos restos posibles para todos los elementos de la array, es decir, {0, 1, 2} . Para segregar estos tres números de tal manera que la suma de dos elementos adyacentes no sea divisible por 3. Sigue los siguientes pasos:

1. Cuente todos los números en tres partes que tengan resto 0 , 1 y 2 . Deje que el conteo sea a , b , y c respectivamente.
2. Ahora organice los números que tienen un resto 0 con los números que tienen un resto 1 o 2 de modo que su suma no sea divisible por 3. A continuación se muestran las condiciones en las que esta condición puede ser cierta: 
   • Si a ≥ 1 y a ≤ b + c + 1
   • Si a y b son iguales a 0 y c > 0
   • Si a y c son iguales a 0 y b > 0
3. Si no hay forma de ordenar todos los números de la manera anterior, entonces no hay permutación tal que la suma de los elementos adyacentes no sea divisible por 3. Por lo tanto, escriba “ No” .
4. Si se determina que la condición del Paso 2 es verdadera, imprima “Sí” .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to checks if any permutation
// of the array exists whose sum of
// adjacent pairs is not divisible by 3
void factorsOf3(int arr[], int N)
{
    int a = 0, b = 0, c = 0;
    for (int i = 0; i < N; i++) {
 
        // Count remainder 0
        if (arr[i] % 3 == 0)
            a++;
 
        // Count remainder 1
        else if (arr[i] % 3 == 1)
            b++;
 
        // Count remainder 2
        else if (arr[i] % 3 == 2)
            c++;
    }
 
    // Condition for valid arrangements
    if (a >= 1 && a <= b + c + 1)
        cout << "Yes" << endl;
    else if (a == 0 && b == 0 && c > 0)
        cout << "Yes" << endl;
    else if (a == 0 && c == 0 && b > 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 2, 3, 3 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    factorsOf3(arr, N);
 
    return 0;
}

// Java program for
// the above approach
class GFG{
 
// Function to checks if any permutation
// of the array exists whose sum of
// adjacent pairs is not divisible by 3
static void factorsOf3(int arr[], int N)
{
  int a = 0, b = 0, c = 0;
  for (int i = 0; i < N; i++)
  {
    // Count remainder 0
    if (arr[i] % 3 == 0)
      a++;
 
    // Count remainder 1
    else if (arr[i] % 3 == 1)
      b++;
 
    // Count remainder 2
    else if (arr[i] % 3 == 2)
      c++;
  }
 
  // Condition for valid arrangements
  if (a >= 1 && a <= b + c + 1)
    System.out.print("Yes" + "\n");
  else if (a == 0 && b == 0 && c > 0)
    System.out.print("Yes" + "\n");
  else if (a == 0 && c == 0 && b > 0)
    System.out.print("Yes" + "\n");
  else
    System.out.print("No" + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array arr[]
  int arr[] = {1, 2, 3, 3};
 
  int N = arr.length;
 
  // Function Call
  factorsOf3(arr, N);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to checks if any permutation
# of the array exists whose sum of
# adjacent pairs is not divisible by 3
def factorsOf3(arr, N):
 
    a = 0
    b = 0
    c = 0
 
    for i in range(N):
 
        # Count remainder 0
        if (arr[i] % 3 == 0):
            a += 1
        # Count remainder 1
        elif (arr[i] % 3 == 1):
            b += 1
        # Count remainder 2
        elif (arr[i] % 3 == 2):
            c += 1
 
    # Condition for valid arrangements
    if (a >= 1 and a <= b + c + 1):
        print("Yes")
    elif (a == 0 and b == 0 and c > 0):
        print("Yes")
    elif (a == 0 and c == 0 and b > 0):
        print("Yes")
    else:
        print("No")
 
# Driver Code
 
# Given array arr[]
arr = [ 1, 2, 3, 3 ]
N = len(arr)
 
# Function call
factorsOf3(arr, N)
 
# This code is contributed by Shivam Singh

// C# program for
// the above approach
using System;
class GFG{
 
// Function to checks if any
// permutation of the array
// exists whose sum of
// adjacent pairs is not
// divisible by 3
static void factorsOf3(int []arr,
                       int N)
{
  int a = 0, b = 0, c = 0;
  for (int i = 0; i < N; i++)
  {
    // Count remainder 0
    if (arr[i] % 3 == 0)
      a++;
 
    // Count remainder 1
    else if (arr[i] % 3 == 1)
      b++;
 
    // Count remainder 2
    else if (arr[i] % 3 == 2)
      c++;
  }
 
  // Condition for valid arrangements
  if (a >= 1 && a <= b + c + 1)
    Console.Write("Yes" + "\n");
  else if (a == 0 && b == 0 && c > 0)
    Console.Write("Yes" + "\n");
  else if (a == 0 && c == 0 && b > 0)
    Console.Write("Yes" + "\n");
  else
    Console.Write("No" + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array []arr
  int []arr = {1, 2, 3, 3};
 
  int N = arr.Length;
 
  // Function Call
  factorsOf3(arr, N);
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program for the above approach
 
// Function to checks if any permutation
// of the array exists whose sum of
// adjacent pairs is not divisible by 3
function factorsOf3(arr, N)
{
    let a = 0, b = 0, c = 0;
    for(let i = 0; i < N; i++)
    {
         
        // Count remainder 0
        if (arr[i] % 3 == 0)
            a++;
         
        // Count remainder 1
        else if (arr[i] % 3 == 1)
            b++;
         
        // Count remainder 2
        else if (arr[i] % 3 == 2)
            c++;
    }
     
    // Condition for valid arrangements
    if (a >= 1 && a <= b + c + 1)
        document.write("Yes" + "<br/>");
    else if (a == 0 && b == 0 && c > 0)
        document.write("Yes" + "<br/>");
    else if (a == 0 && c == 0 && b > 0)
        document.write("Yes" + "<br/>");
    else
        document.write("No" + "<br/>");
}
 
// Driver Code
 
// Given array arr[]
let arr = [ 1, 2, 3, 3 ];
 
let N = arr.length;
 
// Function Call
factorsOf3(arr, N);
 
// This code is contributed by chinmoy1997pal 
 
</script>

Yes

Complejidad temporal: O(N)
Espacio auxiliar: O(1)