Maximize Bitwise OR of Array by incrementing elements by at most K
Given an array arr[], and an integer K, the task is to maximize the bitwise OR of the array arr[], where each element of arr[] can be incremented by almost K.
Examples:
Input: arr[]= {1, 3, 7, 0, 6, 1}, K = 2
Output: [1 3 8 0 6 1]
Explanation: Increase the number 7 by 1 ie 8 after that or of the array is maximum that is 15Input: arr[] ={2, 4, 7, 9}, K = 2
Output: [2, 4, 7, 9]
Explanation: The bitwise OR of arr[] is 15 already so no change is required. 15 is the maximum possible OR.
Approach: This problem can be solved by using Bitwise Operations. Follow the steps below to solve the given problem.
- Find the bitwise or of all the elements, that would tell the status of each bit.
- Start from MSB (Most significant bit), because MSB makes a lot of change in the final bitwise OR.
- If the particular bit of bitwise or is not set. Find the minimum steps to set that bit.
- Minimum Steps to set the ith bit is (1<<i)-((1<<i)-1) & arr[i].
- Count the minimum steps and update the array if the minimum steps are smaller than equal to K.
Below is the implementation of the above approach.
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; void MaximizeBitwiseOR( long a[], int k, int n) { // For storing initial // bitwise OR of array arr[] long oris = 0; long bitwiseOr = 0; for ( int i = 0; i < n; ++i) { bitwiseOr |= a[i]; } for ( int i = 60; i >= 0; i--) { if (((1L << i) & bitwiseOr) == 0) { long minSteps = LONG_MAX; int mini = -1; for ( int j = 0; j < n; j++) { long y = ((1L << i) - 1) & a[j]; long steps = (1L << i) - y; if (steps <= k && steps < minSteps) { minSteps = steps; mini = j; } } if (mini != -1) { k -= minSteps; a[mini] += minSteps; long orr = 0; for ( int j = 0; j < n; j++) { orr |= a[j]; } bitwiseOr = orr; } } } // Print the required result for ( long elements = 0; elements < n; elements++) { if (a[elements]>0) cout << a[elements] << " " ; else cout<<0<< " " ; } } // Driver code int main() { int N = 6; int K = 2; long arr[] = {1, 3, 7, 0, 6, 1}; MaximizeBitwiseOR(arr, K, N); } // This code is contributed by Potta Lokesh |
Java
import java.io.*; class Main { static void MaximizeBitwiseOR( long [] a, int k, int n) { // For storing initial // bitwise OR of array arr[] long or = 0 ; long bitwiseOr = 0 ; for ( int i = 0 ; i < a.length; ++i) { bitwiseOr |= a[i]; } for ( int i = 60 ; i >= 0 ; i--) { if (((1L << i) & bitwiseOr) == 0 ) { long minSteps = Long.MAX_VALUE; int mini = - 1 ; for ( int j = 0 ; j < n; j++) { long y = ((1L << i) - 1 ) & a[j]; long steps = (1L << i) - y; if (steps <= k && steps < minSteps) { minSteps = steps; mini = j; } } if (mini != - 1 ) { k -= minSteps; a[mini] += minSteps; long orr = 0 ; for ( int j = 0 ; j < n; j++) { orr |= a[j]; } bitwiseOr = orr; } } } // Print the required result for ( long elements : a) { System.out.print(elements + " " ); } } // Driver code public static void main(String[] args) { int N = 6 ; int K = 2 ; long arr[] = { 1 , 3 , 7 , 0 , 6 , 1 }; MaximizeBitwiseOR(arr, K, N); } } |
Python3
# Python3 code for the above approach import sys def MaximizeBitwiseOR(a, k, n): # For storing initial # bitwise OR of array arr[] oris = 0 bitwiseOr = 0 for i in range (n): bitwiseOr | = a[i] for i in range ( 60 , - 1 , - 1 ): if ((( 1 << i) & bitwiseOr) = = 0 ): minSteps = sys.maxsize mini = - 1 for j in range (n): y = (( 1 << i) - 1 ) & a[j] steps = ( 1 << i) - y if (steps < = k and steps < minSteps): minSteps = steps mini = j if (mini ! = - 1 ): k - = minSteps a[mini] + = minSteps orr = 0 for j in range (n): orr | = a[j] bitwiseOr = orr # Print the required result for elements in range (n): if (a[elements] > 0 ): print (a[elements], end = " " ) else : print ( 0 , end = " " ) # Driver code if __name__ = = "__main__" : N = 6 K = 2 arr = [ 1 , 3 , 7 , 0 , 6 , 1 ] MaximizeBitwiseOR(arr, K, N) # This code is contributed by ukasp. |
C#
using System; class GFG { static void MaximizeBitwiseOR( long [] a, int k, int n) { // For storing initial // bitwise OR of array arr[] long or = 0; long bitwiseOr = 0; for ( int i = 0; i < a.Length; ++i) { bitwiseOr |= a[i]; } for ( int i = 60; i >= 0; i--) { if (((1L << i) & bitwiseOr) == 0) { long minSteps = Int32.MaxValue; int mini = -1; for ( int j = 0; j < n; j++) { long y = ((1L << i) - 1) & a[j]; long steps = (1L << i) - y; if (steps <= k && steps < minSteps) { minSteps = steps; mini = j; } } if (mini != -1) { k -= ( int )minSteps; a[mini] += minSteps; long orr = 0; for ( int j = 0; j < n; j++) { orr |= a[j]; } bitwiseOr = orr; } } } // Print the required result foreach ( long elements in a) { Console.Write(elements + " " ); } } // Driver code public static void Main() { int N = 6; int K = 2; long []arr = { 1, 3, 7, 0, 6, 1 }; MaximizeBitwiseOR(arr, K, N); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
function MaximizeBitwiseOR(a, k, n) { // For storing initial // bitwise OR of array arr[] let orValue = 0n; let bitwiseOr = 0n; for (let i = 0; i < a.length; ++i) { bitwiseOr |= BigInt(a[i]); } for (let i = 60; i >= 0; i--) { if (((1n << BigInt(i)) & bitwiseOr) == 0n) { let minSteps = Number.MAX_SAFE_INTEGER; let mini = -1; for (let j = 0; j < n; j++) { let y = ((1n << BigInt(i)) - 1n) & BigInt(a[j]); let steps = (1n << BigInt(i)) - y; if (steps <= k && steps < minSteps) { minSteps = Number(steps); mini = j; } } if (mini != -1) { k -= minSteps; a[mini] += minSteps; let orr = 0n; for (let j = 0; j < n; j++) { orr |= BigInt(a[j]); } bitwiseOr = orr; } } } // Print the required result console.log(a.join( " " )); } // Driver code const N = 6; const K = 2; const arr = [1, 3, 7, 0, 6, 1]; MaximizeBitwiseOR(arr, K, N); // This code is contributed by shivhack999 |
Output
1 3 8 0 6 1
Time Complexity: O(N*60)
Auxiliary Space: O(1)