Generate an array having sum of Bitwise OR of same-indexed elements with given array equal to K
Given an array arr[] consisting of N integers and an integer K, the task is to print an array generated such that the sum of Bitwise OR of same indexed elements of the generated array with the given array is equal to K. If it is not possible to generate such an array, then print “-1”.
Examples:
Input: arr[] = {6, 6, 6, 6}, K = 34
Output: 15 7 6 6
Explanation:
Bitwise XOR of same-indexed elements of the arrays {6, 6, 6, 6} and {15, 7, 6, 6} are:
6|15 = 15
6|7 = 7
6|6 = 6
6|6 = 6
Sum of Bitwise ORs = 15 + 7 + 6 + 6 = 34 (= K)Input: arr[] = {1, 2, 3, 4}, K = 32
Output: 23 2 3 4
Approach: Follow the steps below to solve the problem:
- First, calculate the sum of the array arr[] and store it in a variable, say sum.
- Initialize a vector<int>, say B, to store the resultant array.
- Update the value of K as K = K – sum.
- If K is less than 0, print -1.
- Traverse the array arr[] and perform the following operations:
- Initialize a variable, say curr, to store the elements of the resultant array.
- Traverse over the bits of the current array element.
- Check if the current bit is set or not and 2j ≤ K or not. If found to be true, then update curr as curr = curr | (1<<j) and K = K – (1 << j).
- Now, push the curr into the vector B.
- Print the vector B if K is 0. Otherwise, print -1.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the resultant array void constructArr( int A[], int N, int K) { // Stores the sum of the array int sum = 0; // Calculate sum of the array for ( int i = 0; i < N; i++) { sum += A[i]; } // If sum > K if (sum > K) { // Not possible to // construct the array cout << -1 << "\n" ; return ; } // Update K K -= sum; // Stores the resultant array vector< int > B; // Traverse the array for ( int i = 0; i < N; i++) { // Stores the current element int curr = A[i]; for ( int j = 32; j >= 0 and K; j--) { // If jth bit is not set and // value of 2^j is less than K if ((curr & (1LL << j)) == 0 and (1LL << j) <= K) { // Update curr curr |= (1LL << j); // Update K K -= (1LL << j); } } // Push curr into B B.push_back(curr); } // If K is greater than 0 if (!K) { // Print the vector B for ( auto it : B) { cout << it << " " ; } cout << "\n" ; } // Otherwise else { cout << "-1" << "\n" ; } } // Driver Code int main() { // Input int arr[] = { 1, 2, 3, 4 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // Given input int K = 32; // Function call to print // the required array constructArr(arr, N, K); } |
Java
// Java code to implement the approach import java.math.BigInteger; class GFG { // Function to print the resultant array public static void constructArr(BigInteger[] A, int N, BigInteger K) { BigInteger sum = BigInteger.valueOf( 0 ); // Calculating the sum for ( int i = 0 ; i < N; i++) { sum = sum.add(A[i]); } if (sum.compareTo(K) == 1 ) { System.out.println(- 1 ); return ; } // Update K K = K.subtract(sum); // Stores the resultant array BigInteger[] B = new BigInteger[N]; for ( int i = 0 ; i < N; i++) { BigInteger curr = A[i]; BigInteger j = BigInteger.valueOf( 32 ); while (j.compareTo(BigInteger.valueOf( 0 )) == 1 && K.compareTo(BigInteger.valueOf( 0 )) == 1 ) { // If jth bit is not set and // value of 2^j is less than K BigInteger bit = BigInteger.valueOf( 1 ).shiftLeft( j.intValue()); if (curr.and(bit).compareTo( BigInteger.valueOf( 0 )) == 0 && bit.compareTo(K) != 1 ) { // Update curr curr = curr.or(bit); // Update K K = K.subtract(bit); } j = j.subtract(BigInteger.valueOf( 1 )); } // Push curr into B B[i] = curr; } // If K is greater than 0 if (K.compareTo(BigInteger.valueOf( 0 )) == 0 ) { // Print the vector B for ( int i = 0 ; i < N; i++) { System.out.print(B[i] + " " ); } System.out.println(); } // Otherwise else { System.out.println(- 1 ); } } // Driver code public static void main(String[] args) { BigInteger[] arr = new BigInteger[] { BigInteger.valueOf( 1 ), BigInteger.valueOf( 2 ), BigInteger.valueOf( 3 ), BigInteger.valueOf( 4 ) }; int N = arr.length; BigInteger K = BigInteger.valueOf( 32 ); // Function call constructArr(arr, N, K); } } // This code is contributed by phasing17 |
Python3
# Python 3 program for the above approach # Function to print the resultant array def constructArr(A, N, K): # Stores the sum of the array sum = 0 # Calculate sum of the array for i in range (N): sum + = A[i] # If sum > K if ( sum > K): # Not possible to # construct the array print ( - 1 ) return # Update K K - = sum # Stores the resultant array B = [] # Traverse the array for i in range (N): # Stores the current element curr = A[i] j = 32 while (j > = 0 and K > 0 ): # If jth bit is not set and # value of 2^j is less than K if ((curr & ( 1 << j)) = = 0 and ( 1 << j) < = K): # Update curr curr | = ( 1 << j) # Update K K - = ( 1 << j) j - = 1 # Push curr into B B.append(curr) # If K is greater than 0 if (K = = 0 ): # Print the vector B for it in B: print (it, end = " " ) print ( "\n" , end = "") # Otherwise else : print ( "-1" ) # Driver Code if __name__ = = '__main__' : # Input arr = [ 1 , 2 , 3 , 4 ] # Size of the array N = len (arr) # Given input K = 32 # Function call to print # the required array constructArr(arr, N, K) # This code is contributed by ipg2016107. |
C#
// C# program for the above approach using System; class Program { static void constructArr( int [] A, int N, int K) { // Stores the sum of the array int sum = 0; // Calculate sum of the array for ( int i = 0; i < N; i++) { sum += A[i]; } // Update A A[0] += K - sum; // Print the updated array for ( int i = 0; i < N; i++) { Console.Write(A[i] + " " ); } Console.WriteLine(); } static void Main( string [] args) { // Input int [] arr = { 1, 2, 3, 4 }; // Size of the array int N = arr.Length; // Given input int K = 32; // Function call to print // the required array constructArr(arr, N, K); } } |
Javascript
// JavaScript function to implement the approach // Function to print the resultant array function constructArr(A, N, K) { let sum = 0n; // Calculating the sum for (let i = 0; i < N; i++) { sum += A[i]; } if (sum > K) { console.log(-1); return ; } // Update K K -= sum; // Stores the resultant array let B = []; for (let i = 0n; i < BigInt(N); i++) { let curr = BigInt(A[i]); let j = 32n; while (j >= 0n && K > 0n) { // If jth bit is not set and // value of 2^j is less than K if ((curr & (1n << j)) == 0n && (1n << j) <= K) { // Update curr curr |= (1n << j); // Update K K -= (1n << j); } j--; } // Push curr into B B.push(curr); } // If K is greater than 0 if (K == 0n) { // Print the vector B console.log(B.join( " " )); } // Otherwise else { console.log(-1); } } // Driver code let arr = [ 1n, 2n, 3n, 4n ]; let N = arr.length; let K = 32n; // Function call constructArr(arr, N, K); // This code is contributed by phasing17 |
Output:
23 2 3 4
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us