Given an array arr[] of N positive integers and a number K, the task is to find the maximum value of bitwise OR of the subsequence of size K.
Examples:
Input: arr[] = {2, 5, 3, 6, 11, 13}, k = 3
Output: 15
Explanation:
The sub-sequence will maximum OR value is 2, 11, 13.Input: arr[] = {5, 9, 7, 19}, k = 3
Output: 31
Explanation:
The maximum value of bitwise OR of the subsequence of size K = 3 is 31.
Naive Approach: The naive approach is to generate all the subsequence of length K and find the Bitwise OR value of all subsequences. The maximum among all of them will be the answer.
Time Complexity: O(N2)
Auxiliary Space: O(K)
Efficient Approach: To optimize the above method try to implement the Greedy Approach. Below are the steps:
- Initialize an integer array bit[] of size 32 with all value equal to 0.
- Now iterate for each index of bit[] array from 31 to 0, and check if the ith value of bit array is 0 then iterate in the given array and find an element which contributes maximum 1 to our bit array after taking it.
- Take that element and change the bit array correspondingly, also decrease k each time by 1 if k > 0. Otherwise break out from the loop.
- Now convert the bit[] array into a decimal number to get final answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to convert bit array to// decimal numberint build_num(int bit[]){ int ans = 0; for (int i = 0; i < 32; i++) if (bit[i]) ans += (1 << i); // Return the final result return ans;}// Function to find the maximum Bitwise// OR value of subsequence of length Kint maximumOR(int arr[], int n, int k){ // Initialize bit array of // size 32 with all value as 0 int bit[32] = { 0 }; // Iterate for each index of bit[] // array from 31 to 0, and check if // the ith value of bit array is 0 for (int i = 31; i >= 0; i--) { if (bit[i] == 0 && k > 0) { int temp = build_num(bit); int temp1 = temp; int val = -1; for (int j = 0; j < n; j++) { // Check for maximum // contributing element if (temp1 < (temp | arr[j])) { temp1 = temp | arr[j]; val = arr[j]; } } // Update the bit array // if max_contributing // element is found if (val != -1) { // Decrement the value of K k--; for (int j = 0; j < 32; j++) { if (val & (1 << j)) bit[j]++; } } } } // Return the result return build_num(bit);}// Driver Codeint main(){ // Given array arr[] int arr[] = { 5, 9, 7, 19 }; // Length of subsequence int k = 3; int n = sizeof arr / sizeof arr[0]; // Function Call cout << maximumOR(arr, n, k); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to convert bit array to// decimal numberstatic int build_num(int []bit){ int ans = 0; for(int i = 0; i < 32; i++) if (bit[i] == 1) ans += (1 << i); ans += 32; // Return the final result return ans;}// Function to find the maximum Bitwise// OR value of subsequence of length Kstatic int maximumOR(int []arr, int n, int k){ // Initialize bit array of // size 32 with all value as 0 int bit[] = new int[32]; // Iterate for each index of bit[] // array from 31 to 0, and check if // the ith value of bit array is 0 for(int i = 31; i >= 0; i--) { if (bit[i] == 0 && k > 0) { int temp = build_num(bit); int temp1 = temp; int val = -1; for(int j = 0; j < n; j++) { // Check for maximum // contributing element if (temp1 < (temp | arr[j])) { temp1 = temp | arr[j]; val = arr[j]; } } // Update the bit array // if max_contributing // element is found if (val != -1) { // Decrement the value of K k--; for(int j = 0; j < 32; j++) { bit[j]++; } } } } // Return the result return build_num(bit);}// Driver Codepublic static void main(String[] args) { // Given array arr[] int arr[] = { 5, 9, 7, 19 }; // Length of subsequence int k = 3; int n = arr.length; // Function call System.out.println(maximumOR(arr, n, k));}}// This code is contributed by rock_cool |
Python3
# Python3 program to implement# above approach# Function to convert bit array to# decimal numberdef build_num(bit): ans = 0 for i in range(0, 32): if (bit[i]): ans += (1 << i) # Return the final result return ans;# Function to find the maximum Bitwise# OR value of subsequence of length Kdef maximumOR(arr, n, k): # Initialize bit array of # size 32 with all value as 0 bit = [0] * 32 # Iterate for each index of bit[] # array from 31 to 0, and check if # the ith value of bit array is 0 for i in range(31, -1, -1): if (bit[i] == 0 and k > 0): temp = build_num(bit) temp1 = temp val = -1 for j in range(0, n): # Check for maximum # contributing element if (temp1 < (temp | arr[j])): temp1 = temp | arr[j] val = arr[j] # Update the bit array # if max_contributing # element is found if (val != -1): # Decrement the value of K k -= 1 for j in range(0, 32): if (val & (1 << j)): bit[j] += 1 # Return the result return build_num(bit)# Driver Code# Given array arr[]arr = [ 5, 9, 7, 19 ]# Length of subsequencek = 3;n = len(arr)# Function callprint(maximumOR(arr, n, k))# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{// Function to convert bit array to// decimal numberstatic int build_num(int []bit){ int ans = 0; for(int i = 0; i < 32; i++) if (bit[i] == 1) ans += (1 << i); ans += 32; // Return the final result return ans;}// Function to find the maximum Bitwise// OR value of subsequence of length Kstatic int maximumOR(int []arr, int n, int k){ // Initialize bit array of // size 32 with all value as 0 int []bit = new int[32]; // Iterate for each index of bit[] // array from 31 to 0, and check if // the ith value of bit array is 0 for(int i = 31; i >= 0; i--) { if (bit[i] == 0 && k > 0) { int temp = build_num(bit); int temp1 = temp; int val = -1; for(int j = 0; j < n; j++) { // Check for maximum // contributing element if (temp1 < (temp | arr[j])) { temp1 = temp | arr[j]; val = arr[j]; } } // Update the bit array // if max_contributing // element is found if (val != -1) { // Decrement the value of K k--; for(int j = 0; j < 32; j++) { bit[j]++; } } } } // Return the result return build_num(bit);}// Driver Codepublic static void Main() { // Given array arr[] int []arr = { 5, 9, 7, 19 }; // Length of subsequence int k = 3; int n = arr.Length; // Function call Console.Write(maximumOR(arr, n, k));}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript program for the above approach// Function to convert bit array to// decimal numberfunction build_num(bit){ let ans = 0; for(let i = 0; i < 32; i++) if (bit[i] > 0) ans += (1 << i); // Return the final result return ans;}// Function to find the maximum Bitwise// OR value of subsequence of length Kfunction maximumOR(arr, n, k){ // Initialize bit array of // size 32 with all value as 0 let bit = new Array(32); bit.fill(0); // Iterate for each index of bit[] // array from 31 to 0, and check if // the ith value of bit array is 0 for(let i = 31; i >= 0; i--) { if (bit[i] == 0 && k > 0) { let temp = build_num(bit); let temp1 = temp; let val = -1; for(let j = 0; j < n; j++) { // Check for maximum // contributing element if (temp1 < (temp | arr[j])) { temp1 = temp | arr[j]; val = arr[j]; } } // Update the bit array // if max_contributing // element is found if (val != -1) { // Decrement the value of K k--; for(let j = 0; j < 32; j++) { if ((val & (1 << j)) > 0) bit[j]++; } } } } // Return the result return build_num(bit);} // Driver code// Given array arr[]let arr = [ 5, 9, 7, 19 ];// Length of subsequencelet k = 3;let n = arr.length;// Function Calldocument.write(maximumOR(arr, n, k)); // This code is contributed by divyeshrabadiya07 </script> |
Output:
31
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Similar article: Maximum Bitwise AND value of subsequence of length K
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!
