Given an integer N denoting the size of an array and the bitwise AND (K) of all elements of the array. The task is to determine whether the total sum of the elements is odd or even or cannot be determined.
Examples:
Input: N = 1, K = 11
Output: Odd
Explanation: As there is only one element in the array, the element itself is 11.Input: N = 1, K = 2
Output: Even
Explanation: As there is only one element in the array. the element itself is 2.Input: N = 5, K = 4
Output: Impossible
Approach: The solution to the problem is based on the below observation:
Observation:
- We know that for bitwise AND to be 1, all the bits must be 1.
- So if the given LSB of given bitwise AND of Array is 1, it must mean that LSB of all the elements of Array must have been 1.
- On the other hand, if the LSB of given bitwise AND of Array is 0, it can mean that either all or some of the elements of Array has 0 in their LSB.
Conclusion: Therefore using above observation, it can be said that:
- For bitwise AND to be odd, all the elements of the array must be odd, as LSB of odd numbers is always 1.
- But if the bitwise AND is even, then nothing can be said about the parity (odd or even) of all the elements.
Follow the steps mentioned below to solve the problem:
- If the LSB of K is 1, it clearly proves that every number has LSB as 1 i.e., every number is odd because if any single number has LSB 0 then LSB of K will be 0.
- The sum of N odd number is always odd if N is odd.
- The sum is even and if N is even.
- If the LSB of K is 0 the sum cannot be determined except for the case when N is 1 i.e. when N is 1 sum depends on the parity of K. In another case, it’s impossible to find as the count of even and odd numbers cannot be determined.
Below is the implementation of the above approach.
C++
// 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 codeint main(){ long int N, K; N = 5, K = 4; findtotalsum(N, K); return 0;} |
Java
// Java code to minimize number of rotationsimport 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 is contributed by hrithikgarg03188. |
Python3
# 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 codeN = 5K = 4findtotalsum(N, K)# This code is contributed by sanjoy_62. |
C#
// C# code to minimize number of rotationsusing 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 is contributed by Samim Hossain Mondal. |
Javascript
<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> |
Output
Impossible
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
