Minimize Or of Remaining Elements Using Operations in Java
We are given an integer k and an integer array nums, which is 0-indexed.
Choose any index i of nums such that 0 = i < nums.length - 1 and replace nums[i] and nums[i + 1] with a single instance of nums[i] & nums[i + 1], where & stands for the bitwise AND operator, in a single operation.
After doing a maximum of k operations, return the lowest value that can be obtained from the bitwise OR of the remaining items of nums.
Examples:
Example 1:
Input: nums = [ 3, 5, 3, 2, 7 ] k = 2
Output: 3
Explanation:
- Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [1,3,2,7].
- Replace nums[2] and nums[3] with (nums[2] & nums[3]) so that nums becomes equal to [1,3,2].
The bitwise-or of the final array is 3.
It can be shown that 3 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.
Example 2:
Input: nums = [ 7, 3, 15, 14, 2, 8 ], k = 4
Output: 2
Explanation:
- Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [3,15,14,2,8].
- Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [3,14 2,8].
- Replace nums[0] and nums[1] with (nums[0] & nums[1]) so that nums becomes equal to [2,2,8].
- Replace nums[1] and nums[2] with (nums[1] & nums[2]) so that nums becomes equal to [2,0].
The bitwise-or of the final array is 2.
It can be shown that 2 is the minimum possible value of the bitwise OR of the remaining elements of nums after applying at most k operations.
Example 3:
Input: nums = [ 10, 7, 10, 3, 9, 14, 9, 4 ], k = 1
Output: 15
Explanation: Without applying any operations, the bitwise-or of nums is 15.It can be shown that 15 is the minimum possible value of the bitwise OR of the remaining elementof nums after applying at most k operations.
Example 4:
Input: arr[] = [ 2, 7, 4, 1, 8, 1 ]
Output: 1
Explanation:
Removing the pair (arr[0], arr[2]) from arr[] and inserting abs(arr[0] – arr[2]) into arr[] modifies arr[] to { 2, 7, 1, 8, 1 }.
Removing the pair (arr[1], arr[3]) from arr[] and inserting abs(arr[1] – arr[3]) into arr[] modifies arr[] to { 2, 1, 1, 1 }.
Removing the pair (arr[0], arr[1]) from arr[] and inserting abs(arr[0] – arr[1]) into arr[] modifies arr[] to { 1, 1, 1 }.
Removing the pair (arr[0], arr[1]) from arr[] modifies arr[] to { 1 }.
Therefore, the required output is 1.
Example 5:
Input: arr[] = [ 1, 1, 4, 2, 2 ]
Output: 0
Approach 1: Using dynamic programming
ALGORITHM:
Step 1: Initialize a 2D array, say dp[][], to store the minimum difference of subset sums that can be obtained upto the ith element.
Step 2: Use the above recurrence relation and calculate the value of dp[N][sum].
Step 3: Finally, print the value of dp[N][sum] as the required sum.
Filename: NumDp.java
import java.util.*; import java.lang.*; public class NumDp { // Function to find the smallest element // left in the array by the given operations static int smallestLeft(int arr[], int total, int sum, int i, int[][] dp) { // Base Case if (i == 0) { return Math.abs(total - 2 * sum); } // If this subproblem // has occurred previously if (dp[i][sum] != -1) return dp[i][sum]; // Including i-th array element // into the first subset int X = smallestLeft(arr, total, sum + arr[i - 1], i - 1, dp); // If i-th array element is not selected int Y = smallestLeft(arr, total, sum, i - 1, dp); // Update dp[i][sum] return dp[i][sum] = Math.min(X, Y); } // Utility function to find smallest element // left in the array by the given operations static void UtilSmallestElement(int arr[], int N) { // Stores sum of // the array elements int total = 0; // Traverse the array for (int i = 0; i < N; i++) { // Update total total += arr[i]; } // Stores overlapping // subproblems int[][] dp = new int[N + 1][total]; for(int[] k:dp) Arrays.fill(k, -1); System.out.println(smallestLeft(arr, total, 0, N, dp)); } // Driver function public static void main (String[] args) { int arr[] = { 2, 7, 4, 1, 8, 1 }; int N = arr.length; UtilSmallestElement(arr, N); } }
Output:
1
Complexity analysis:
Time complexity: The time complexity of the program is O(N * sum), where sum is the sum of the array elements.
Space complexity: The space complexity of the program is O(N * sum).
Approach 2: Using tabulation method
ALGORITHM:
Step 1: Initialize an array, say dp[], where dp[i] checks if the sum i can be obtained as the sum of a subset of the given array.
Step 2: Traverse the array and calculate the sum of array elements and store it in a variable, say totalSum.
Step 3: Using the above recurrence relation, find the closest value of (totalSum] / 2), say X, such that dp[X] is true.
Step 4: Finally, print the value of (totalSum – 2 * X).
Filename: TabMethod.java
import java.util.*; public class TabMethod { // Function to find minimize the remaining // array element by removing pairs and // replacing them by their absolute difference static int SmallestElementLeft(int arr[], int N) { // Stores sum of array elements int totalSum = 0; // Traverse the array for(int i = 0; i < N; i++) { // Update totalSum totalSum += arr[i]; } // Stores half of totalSum int req = totalSum / 2; // dp[i]: True if sum i can be // obtained as a subset sum boolean[] dp = new boolean[req + 1]; // Initialize dp[] array Arrays.fill(dp, false); // Base case dp[0] = true; // Stores closest sum that can // be obtained as a subset sum int reach = 0; // Traverse the array for(int i = 0; i < N; i++) { // Iterate over all possible value of sum for(int j = req; j - arr[i] >= 0; j--) { // Update dp[j] dp[j] = dp[j] || dp[j - arr[i]]; // If sum i can be obtained // from array elements if (dp[j]) { // Update reach reach = Math.max(reach, j); } } } return totalSum - (2 * reach); } // Driver Code public static void main(String[] args) { int arr[] = { 2, 2, 2 }; int N = arr.length; System.out.print(SmallestElementLeft(arr, N)); } }
Output:
2
Complexity analysis:
Time complexity: The time complexity of the program is O(N * sum), where sum is the sum of the array elements.
Space complexity: The space complexity of the program is O(sum).