Maximum bitwise OR value of subsequence of length K in Java
The maximum bitwise OR value of subsequences of length K is a complex problem in computer science and mathematics involving the bitwise OR operation. It involves identifying the optimal combination of bits across subsequences. The quest offers insights into binary representation and combinatorial optimization, highlighting computational efficiency and mathematical elegance.
Example:
Input: arr[] = {5, 9, 7, 19}, k = 3
Output: 31
Explanation: The subsequence of size K = 3 has a maximum bitwise OR value of 31.
Using Naive Approach
Algorithm
Step1: Initialize maxOR to 0.
Step2: Iterate from 0 to 2^n - 1.
Step3: Check if the number of set bits in the current iteration is equal to k.
Step 4: If yes, calculate the bitwise OR value of the corresponding subsequence.
Step 5: Update maxOR with the maximum bitwise OR value found so far.
Step 6: Return maxOR.
Here is an implementation of finding the maximum bitwise OR value using a naive approach :
FileName:MaximumBitwiseOR.java
public class MaximumBitwiseOR { // Function to calculate maximum bitwise OR public static int maxBitwiseOR(int[] arr, int k) { int n = arr.length; int maxOR = 0; // Generate all subsequences of length k for (int i = 0; i < (1 << n); i++) { // Check if the number of set bits in i is equal to k if (Integer.bitCount(i) == k) { // Variable to store the bitwise OR value of the subsequence int bitwiseOR = 0; // Calculate the bitwise OR value for the current subsequence for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { bitwiseOR |= arr[j]; } } // Update maxOR with the maximum value encountered so far maxOR = Math.max(maxOR, bitwiseOR); } } return maxOR; } public static void main(String[] args) { int[] arr = {5, 9, 7, 19}; int k = 3; System.out.println(maxBitwiseOR(arr, k)); } }
Output:
31
Complexity analysis: The time complexity for the above naive approach is O(2^n * n), where n is the length of the input array and the space Complexity is O(1), the space used is independent of the input size.
Using Optimized Approach
Algorithm
Step1: Initialize a 32-bit bit array with all values set to 0.
Step 2: Iterate over each index from 31 to 0.
Step3: Check the current bit and lengthK.
Step 4: Calculate a temporary value based on the current state.
Step 5: Iterate over the input array and perform bitwise OR operation with temporary value.
Step 6: Update the temporary value if greater than the previous value.
Step7: Update bit array if contributing element found.
Step8: Decrement lengthK value and repeat steps until all bits are processed or lengthK equals 0.
Step9 : Return the decimal value of the bit array.
Here is an implementation of finding the maximum biwise OR value using an optimized approach :
FileName:MaximumBitwiseOR1.java
public class MaximumBitwiseOR1 { // Function to convert bit array to decimal number static int buildNumber(int[] bitArray) { int result = 0; for (int i = 0; i < 32; i++) if (bitArray[i] == 1) result += (1 << i); result += 32; return result; } // Function to find the maximum Bitwise OR value of subsequence of length K static int maximumORValue(int[] array, int size, int lengthK) { // Initialize bit array of size 32 with all values as 0 int[] bitArray = new int[32]; for (int i = 31; i >= 0; i--) { if (bitArray[i] == 0 && lengthK > 0) { int temp = buildNumber(bitArray); int temp1 = temp; int val = -1; for (int j = 0; j < size; j++) { // Check for the maximum contributing element if (temp1 < (temp | array[j])) { temp1 = temp | array[j]; val = array[j]; } } // Update the bit array if max_contributing element is found if (val != -1) { // Decrement the value of K lengthK--; for (int j = 0; j < 32; j++) { bitArray[j]++; } } } } return buildNumber(bitArray); } public static void main(String[] args) { int inputArray[] = { 5, 9, 7, 19 }; int lengthK = 3; int size = inputArray.length; System.out.println(maximumORValue(inputArray, size, lengthK)); } }
Output:
31
Complexity analysis: The time complexity of the above approach is O(32 * n * k), where n is the size of the input array and k is the length of the subsequence. The space complexity is also O(32), as it uses a fixed-size bit array of length 32 to store the bitwise OR operations.