Verifique si la suma de la array original es impar o par usando Bitwise AND of Array

Dado un número entero N que denota el tamaño de una array y el AND bit a bit (K) de todos los elementos de la array. La tarea es determinar si la suma total de los elementos es par o impar o no se puede determinar.

Ejemplos:

Entrada : N = 1, K = 11
Salida: Impar
Explicación: Como solo hay un elemento en la array, el elemento en sí es 11.

Entrada: N = 1, K = 2
Salida: Par
Explicación: Como solo hay un elemento en la array. el elemento en sí es 2.

Entrada: N= 5, K = 4
Salida: Imposible

Enfoque: La solución al problema se basa en la siguiente observación: 
 

Observación: 
 

• Sabemos que para que AND bit a bit sea 1, todos los bits deben ser 1 . 
   
• Entonces, si el LSB dado de AND bit a bit dado de Array es 1, debe significar que el LSB de todos los elementos de Array debe haber sido 1.
• Por otro lado, si el LSB de AND bit a bit dado de Array es 0, puede significar que todos o algunos de los elementos de Array tienen 0 en su LSB.

Conclusión: Por lo tanto, utilizando la observación anterior, se puede decir que: 
 

• Para que AND bit a bit sea impar , todos los elementos de la array deben ser impares, ya que el LSB de los números impares siempre es 1.
• Pero si el AND bit a bit es par , entonces no se puede decir nada sobre la paridad (par o impar) de todos los elementos.

Siga los pasos que se mencionan a continuación para resolver el problema:

• Si el LSB de K es 1 , claramente prueba que cada número tiene LSB como 1, es decir, cada número es impar porque si un solo número tiene LSB 0, entonces el LSB de K será 0.
  • La suma de N números impares siempre es impar si N es impar.
  • La suma es par y si N es par.
• Si el LSB de K es 0, la suma no puede determinarse excepto en el caso en que N sea 1, es decir, cuando N sea 1 , la suma depende de la paridad de K. En otro caso, es imposible encontrarlo ya que no se puede determinar el conteo de números pares e impares.

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find whether the sum is even,
// odd or impossible to find.
void findtotalsum(int n, int a)
{
    // Separate case when N is 1
    // as it depend on parity of n
    if (n == 1) {
        if (a % 2 == 0)
            cout << "Even" << endl;
        else
            cout << "Odd" << endl;
    }
 
    // Check if a is odd
    else if (a % 2 != 0) {
 
        // Checking whether n is odd or even
        if (n % 2 == 0)
            cout << "Even" << endl;
        else
            cout << "Odd" << endl;
    }
    else {
 
        // When no condition applies
        // its impossible to find sum
        cout << "Impossible" << endl;
    }
}
 
// Driver code
int main()
{
    long int N, K;
    N = 5, K = 4;
    findtotalsum(N, K);
    return 0;
}

// Java code to minimize number of rotations
import java.util.*;
 
class GFG {
 
  // Function to find whether the sum is even,
  // odd or impossible to find.
  static void findtotalsum(int n, int a)
  {
 
    // Separate case when N is 1
    // as it depend on parity of n
    if (n == 1) {
      if (a % 2 == 0)
        System.out.println("Even");
      else
        System.out.println("Odd");
    }
 
    // Check if a is odd
    else if (a % 2 != 0) {
 
      // Checking whether n is odd or even
      if (n % 2 == 0)
        System.out.println("Even");
      else
        System.out.println("Odd");
    }
    else {
 
      // When no condition applies
      // its impossible to find sum
      System.out.println("Impossible");
    }
  }
 
  // Driver code
  public static void main (String[] args) {
    int N = 5, K = 4;
    findtotalsum(N, K);
  }
}
 
// This code i contributed by hrithikgarg03188.

# Python program for the above approach
 
# Function to find whether the sum is even,
# odd or impossible to find.
def findtotalsum(n, a) :
 
    # Separate case when N is 1
    # as it depend on parity of n
    if (n == 1) :
        if (a % 2 == 0) :
            print("Even")
        else :
            print( "Odd" )
     
 
    # Check if a is odd
    elif (a % 2 != 0) :
 
        # Checking whether n is odd or even
        if (n % 2 == 0) :
            print("Even")
        else :
            print( "Odd" )
     
    else :
 
        # When no condition applies
        # its impossible to find sum
        print( "Impossible")
     
# Driver code
 
N = 5
K = 4
findtotalsum(N, K)
 
# This code is contributed by sanjoy_62.

// C# code to minimize number of rotations
using System;
 
class GFG {
 
  // Function to find whether the sum is even,
  // odd or impossible to find.
  static void findtotalsum(int n, int a)
  {
 
    // Separate case when N is 1
    // as it depend on parity of n
    if (n == 1) {
      if (a % 2 == 0)
        Console.WriteLine("Even");
      else
        Console.WriteLine("Odd");
    }
 
    // Check if a is odd
    else if (a % 2 != 0) {
 
      // Checking whether n is odd or even
      if (n % 2 == 0)
        Console.WriteLine("Even");
      else
        Console.WriteLine("Odd");
    }
    else {
 
      // When no condition applies
      // its impossible to find sum
      Console.WriteLine("Impossible");
    }
  }
 
  // Driver code
  public static void Main () {
    int N = 5, K = 4;
    findtotalsum(N, K);
  }
}
 
// This code i contributed by Samim Hossain Mondal.

<script>
    // JavaScript code to implement the above approach
 
    // Function to find whether the sum is even,
    // odd or impossible to find.
    const findtotalsum = (n, a) => {
     
        // Separate case when N is 1
        // as it depend on parity of n
        if (n == 1) {
            if (a % 2 == 0)
                document.write("Even<br/>");
            else
                document.write("Odd<br/>");
        }
 
        // Check if a is odd
        else if (a % 2 != 0) {
 
            // Checking whether n is odd or even
            if (n % 2 == 0)
                document.write("Even<br/>");
            else
                document.write("Odd<br/>");
        }
        else {
 
            // When no condition applies
            // its impossible to find sum
            document.write("Impossible<br/>");
        }
    }
 
    // Driver code
    let N, K;
    N = 5, K = 4;
    findtotalsum(N, K);
 
// This code is contributed by rakeshsahni
 
</script>

Impossible

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)