Minimize steps to make Array elements equal by deleting adjacent pair and inserting bitwise OR
Given an array arr[], consisting of N integers, the task is to find the minimum number of moves required to make all numbers in the resulting array equal. In one move,
- Take two adjacent numbers arr[i] and arr[i+1], and delete them.
- Insert the bitwise OR of arr[i] and arr[i+1] at the deleted position.
Examples:
Input: arr[] = {1, 1, 1, 0, 1}
Output: 1
Explanation: After OR operation on arr[2] and arr[3] we get, 1 | 0 = 1.
Since, array arr[] becomes {1, 1, 1, 1} and here all elements are equal.
Thus, it takes only 1 move to make all the numbers equal.Input: arr[] = {1, 2, 3}
Output: 1
Explanation: After OR operation on arr[0] and arr[1] we get, 1 | 2 = 3.
Now, array arr[] becomes {3, 3} and here both elements are equal.
Thus, it takes only 1 move to make all the numbers equal.
Approach: The problem can be solved based on the following observation of bitwise properties:
It is known that x | x = x, [where ‘|’ means bitwise OR].
Lets say that the array has all the elements as X at the end and total M elements.
Based on this we can assume that there were M subarrays such that bitwise OR of the subarray elements are X.The closer the value of M to N, the less operations are done.
So the task reduces to find the maximum number of subarray such that they have bitwise OR = XIf there are M such subarrays, then the number of operations performed = N – M (because in each step size reduces by 1)
Follow the below steps to solve the problem:
- Find bitwise OR of all array elements and store it (say Total_Or).
- Initialize a variable (say Group = 0) to count how many subarrays have the OR value of Total_Or.
- Run a loop in the array from i = 0 to N:
- Calculate the bitwise OR of the elements (say Current_Or).
- If Current_Or is the same as Total_Or, Increment Group by 1 and set Current_Or = 0;
- After executing the loop, return N – Group.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to return minimum number of moves int findMinMoves( int * arr, int n) { // Initialize the variables int Total_Or = 0; int Current_Or = 0; int Group = 0; // Find or of all array elements for ( int i = 0; i < n; i++) { Total_Or |= arr[i]; } // Find number of groups forming or // equal to Total_Or for ( int i = 0; i < n; i++) { Current_Or |= arr[i]; // If Current_Or = Total_Or, // increment Group by 1 if (Current_Or == Total_Or) { Group++; // Reset Current_Or Current_Or = 0; } } // Return minimum number of moves return n - Group; } // Driver Code int main() { int arr[] = { 1, 1, 1, 0, 1 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findMinMoves(arr, N); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Java code to implement the above approach // Function to return minimum number of moves static int findMinMoves( int arr[], int n) { // Initialize the variables int Total_Or = 0 ; int Current_Or = 0 ; int Group = 0 ; // Find or of all array elements for ( int i = 0 ; i < n; i++) { Total_Or |= arr[i]; } // Find number of groups forming or // equal to Total_Or for ( int i = 0 ; i < n; i++) { Current_Or |= arr[i]; // If Current_Or = Total_Or, // increment Group by 1 if (Current_Or == Total_Or) { Group++; // Reset Current_Or Current_Or = 0 ; } } // Return minimum number of moves return n - Group; } // Driver Code public static void main(String args[]) { int arr[] = { 1 , 1 , 1 , 0 , 1 }; int N = arr.length; // Function call System.out.println(findMinMoves(arr, N)); } } // This code is contributed by shinjanpatra |
Python3
# Python3 code to implement the above approach # Function to return minimum number of moves def findMinMoves(arr,n): # Initialize the variables Total_Or = 0 ; Current_Or = 0 ; Group = 0 ; # Find or of all array elements for i in range ( 0 ,n): Total_Or = Total_Or|arr[i] # Find number of groups forming or # equal to Total_Or for i in range ( 0 ,n): Current_Or | = arr[i] # If Current_Or = Total_Or, # increment Group by 1 if (Current_Or = = Total_Or): Group = Group + 1 # Reset Current_Or Current_Or = 0 # Return minimum number of moves return n - Group # Driver Code N = 5 arr = [ 1 , 1 , 1 , 0 , 1 ] # Function call print (findMinMoves(arr, N)) # This code is contributed by akashish__ |
C#
using System; public class GFG{ // Function to return minimum number of moves static int findMinMoves( int [] arr, int n) { // Initialize the variables int Total_Or = 0; int Current_Or = 0; int Group = 0; // Find or of all array elements for ( int i = 0; i < n; i++) { Total_Or |= arr[i]; } // Find number of groups forming or // equal to Total_Or for ( int i = 0; i < n; i++) { Current_Or |= arr[i]; // If Current_Or = Total_Or, // increment Group by 1 if (Current_Or == Total_Or) { Group++; // Reset Current_Or Current_Or = 0; } } // Return minimum number of moves return n - Group; } public static void Main () { // Code int N = 5; int [] arr = { 1, 1, 1, 0, 1 }; // Function call int ans = findMinMoves(arr, N); Console.WriteLine(ans); } } // This code is contributed by akashish__ |
Javascript
<script> // JavaScript code for the above approach // Function to return minimum number of moves function findMinMoves(arr, n) { // Initialize the variables let Total_Or = 0; let Current_Or = 0; let Group = 0; // Find or of all array elements for (let i = 0; i < n; i++) { Total_Or |= arr[i]; } // Find number of groups forming or // equal to Total_Or for (let i = 0; i < n; i++) { Current_Or |= arr[i]; // If Current_Or = Total_Or, // increment Group by 1 if (Current_Or == Total_Or) { Group++; // Reset Current_Or Current_Or = 0; } } // Return minimum number of moves return n - Group; } // Driver Code let arr = [1, 1, 1, 0, 1]; let N = arr.length; // Function call document.write(findMinMoves(arr, N)); // This code is contributed by Potta Lokesh </script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)