Minimize Bitwise XOR of array elements with 1 required to make sum of array at least K
Given an array arr[] consisting of N positive integers and a positive integer K, the task is to count minimum Bitwise XOR of array elements with 1 required such that the sum of the array is at least K.
Examples:
Input: arr[] = {0, 1, 1, 0, 1}, K = 4
Output: 1
Explanation: Performing Bitwise XOR of arr[0] and 1 modifies arr[] to {1, 1, 1, 0, 1}. Now, the sum of array = 1 + 1 + 1 + 0 + 1 = 4(= K).Input: arr[] = {14, 0, 1, 0}, K = 20
Output: -1
Approach: The given problem can be solved using the fact that Bitwise XOR of 1 with an even element increases the element by 1.
Follow the steps below to solve the problem:
- Find the sum of the given array arr[] and store it in a variable say S.
- Count the number of even elements in the array and store it in a variable, say E.
- If S is greater than or equal to K, then print 0.
- Otherwise, if the value of S + E is less than K, then print -1.
- Otherwise, print the value of (K – S) as the minimum number of Bitwise XOR of an array element with 1 is required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum number // of Bitwise XOR of array elements // with 1 required to make sum of // the array at least K int minStepK( int arr[], int N, int K) { // Stores the count of // even array elements int E = 0; // Stores sum of the array int S = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Increment sum S += arr[i]; // If array element is even if (arr[i] % 2 == 0) // Increase count of even E += 1; } // If S is at least K if (S >= K) return 0; // If S + E is less than K else if (S + E < K) return -1; // Otherwise, moves = K - S else return K - S; } // Driver Code int main() { int arr[] = { 0, 1, 1, 0, 1 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 4; cout << minStepK(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find minimum number // of Bitwise XOR of array elements // with 1 required to make sum of // the array at least K static int minStepK( int arr[], int N, int K) { // Stores the count of // even array elements int E = 0 ; // Stores sum of the array int S = 0 ; // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Increment sum S += arr[i]; // If array element is even if (arr[i] % 2 == 0 ) // Increase count of even E += 1 ; } // If S is at least K if (S >= K) return 0 ; // If S + E is less than K else if (S + E < K) return - 1 ; // Otherwise, moves = K - S else return K - S; } // Driver code public static void main(String[] args) { int arr[] = { 0 , 1 , 1 , 0 , 1 }; int N = arr.length; int K = 4 ; System.out.println(minStepK(arr, N, K)); } } // This code is contributed by offbeat |
Python3
# Python 3 program for the above approach # Function to find minimum number # of Bitwise XOR of array elements # with 1 required to make sum of # the array at least K def minStepK(arr, N, K): # Stores the count of # even array elements E = 0 # Stores sum of the array S = 0 # Traverse the array arr[] for i in range (N): # Increment sum S + = arr[i] # If array element is even if (arr[i] % 2 = = 0 ): # Increase count of even E + = 1 # If S is at least K if (S > = K): return 0 # If S + E is less than K elif (S + E < K): return - 1 # Otherwise, moves = K - S else : return K - S # Driver Code if __name__ = = "__main__" : arr = [ 0 , 1 , 1 , 0 , 1 ] N = len (arr) K = 4 print (minStepK(arr, N, K)) # This code is contributed by ukasp. |
C#
// C# program for the above approach using System; class GFG { // Function to find minimum number // of Bitwise XOR of array elements // with 1 required to make sum of // the array at least K static int minStepK( int [] arr, int N, int K) { // Stores the count of // even array elements int E = 0; // Stores sum of the array int S = 0; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Increment sum S += arr[i]; // If array element is even if (arr[i] % 2 == 0) // Increase count of even E += 1; } // If S is at least K if (S >= K) return 0; // If S + E is less than K else if (S + E < K) return -1; // Otherwise, moves = K - S else return K - S; } // Driver Code public static void Main() { int [] arr= { 0, 1, 1, 0, 1 }; int N = arr.Length; int K = 4; Console.WriteLine(minStepK(arr, N, K)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach // Function to find minimum number // of Bitwise XOR of array elements // with 1 required to make sum of // the array at least K function minStepK(arr, N, K) { // Stores the count of // even array elements var E = 0; // Stores sum of the array var S = 0; // Traverse the array arr[] for ( var i = 0; i < N; i++) { // Increment sum S += arr[i]; // If array element is even if (arr[i] % 2 === 0) // Increase count of even E += 1; } // If S is at least K if (S >= K) return 0; // If S + E is less than K else if (S + E < K) return -1; // Otherwise, moves = K - S else return K - S; } // Driver Code var arr = [ 0, 1, 1, 0, 1 ]; var N = arr.length; var K = 4; document.write(minStepK(arr, N, K)); // This code is contributed by rdtank </script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us