Find arrangement of Array such that prefix OR is maximum for each index
Given an array arr[] consisting of N non-negative integers. The task is to find a rearrangement of the array such that the prefix OR for each index is maximum among all possible arrangements.
Examples:
Input: N = 4, arr[] = [1, 2, 4, 8]
Output: [8, 4, 2, 1]
Explanation: Prefix of the rearranged array is [8, 8 | 4, 8 | 4 | 2, 8 | 4 | 2 | 1] = [8, 12, 14, 15].Input: N = 6, arr[] = [2, 3, 4, 2, 3, 4]
Output : [4, 3, 2, 2, 3, 4]
Explanation: Prefix of the rearranged array is [4, 4 | 3, 4 | 3 | 2, 4 | 3 | 2 | 2, 4 | 3 | 2 | 2 | 3, 4 | 3 | 2 | 2 | 3 | 4] = [4, 7, 7, 7, 7, 7].Input: N = 2, arr[] = [1, 2]
Output: [2, 1]
Approach:
We can make the observation that only the first log2(maxval) elements matter, Since after placing them optimally we can be sure that all possible bits that could be set in the prefix OR would have already been set.
So, we can brute force the optimal choice log2(maxval) times (we choose to add an element if it provides the largest new prefix OR value among all unused elements) and then just add the rest of the unused elements. [maxvalue represents the maximum value in the array].
Follow the steps mentioned below to implement the approach.
- Create a dummy array (say temp[]) of size N, to store the final result.
- Create a visited array (say vis[]) of size N to check whether an element is previously visited or not and initialize it with false.
- Initialize a variable cur_or with 0 for calculating the prefix OR.
- Start iterating from min(30, N) to 0 [as a maximum of 30 bits can be set].
- Initialize a variable mx to store the maximum prefix OR at every position, and another variable idx to the index from where the maximum prefix OR is calculated.
- Iterate from 0 to N and do the following operation
- if the element is previously visited then skip it.
- if ( cur_or | arr[j] ) is greater than mx then update (max_or) with ( cur_or | arr[j] ) and update idx with j.
- Update vis[idx] with true, temp[k++] with arr[idx] where k maintains the index where the next element will be placed in the temporary array.
- Put the remaining unvisited elements in the temporary array.
- Update array arr[] with temp.
Below is the Implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function performing calculation void solve( int n, vector< int >& arr) { vector< int > temp(n); int j = 0; vector< int > vis(n, false ); int cur_or = 0; // Loop to calculate the maximum prefix for ( int i = min(n, 30); i > 0; i--) { int mx = 0; int idx = -1; for ( int j = 0; j < n; j++) { if (vis[j]) continue ; // If temp maximum element is // smaller than (previous or | current element) // then update temporary max if (mx < (cur_or | arr[j])) { mx = (cur_or | arr[j]); idx = j; } } vis[idx] = true ; // Storing the element in the temp array temp[j++] = arr[idx]; cur_or = (cur_or | arr[idx]); } for ( int i = 0; i < n; i++) { // Storing remaining element in the temp array if (!vis[i]) { temp[j++] = arr[i]; } } arr = temp; } // Function for printing the array void print(vector< int >& arr, int n) { for ( int i = 0; i < n; i++) { cout << arr[i] << " " ; } cout << endl; } // Driver Code int main() { vector< int > arr = { 1, 2, 4, 8 }; int N = arr.size(); solve(N, arr); print(arr, N); vector< int > arr2 = { 1, 2 }; N = arr2.size(); solve(N, arr2); print(arr2, N); vector< int > arr3 = { 2, 3, 4, 2, 3, 4 }; N = arr3.size(); solve(N, arr3); print(arr3, N); vector< int > arr4 = { 10 }; N = arr4.size(); solve(N, arr3); print(arr4, N); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { // Function performing calculation static void solve( int n, int [] arr) { int [] temp = new int [n]; int j = 0 ; boolean vis[] = new boolean [n]; int cur_or = 0 ; // Loop to calculate the maximum prefix for ( int i = Math.min(n, 30 ); i > 0 ; i--) { int mx = 0 ; int idx = - 1 ; for ( int jj = 0 ; jj < n; jj++) { if (vis[jj]) continue ; // If temp maximum element is // smaller than (previous or | current element) // then update temporary max if (mx < (cur_or | arr[jj])) { mx = (cur_or | arr[jj]); idx = jj; } } vis[idx] = true ; // Storing the element in the temp array temp[j++] = arr[idx]; cur_or = (cur_or | arr[idx]); } for ( int i = 0 ; i < n; i++) { // Storing remaining element in the temp array if (!vis[i]) { temp[j++] = arr[i]; } } for ( int i= 0 ;i<n;i++){ arr[i] = temp[i]; } } // Function for printing the array static void print( int [] arr, int n) { for ( int i = 0 ; i<n ; i++) { System.out.print(arr[i] + " " ); } System.out.println(); } public static void main(String[] args) { int [] arr = { 1 , 2 , 4 , 8 }; int N = arr.length; solve(N, arr); print(arr, N); int [] arr2 = { 1 , 2 }; N = arr2.length; solve(N, arr2); print(arr2, N); int [] arr3 = { 2 , 3 , 4 , 2 , 3 , 4 }; N = arr3.length; solve(N, arr3); print(arr3, N); int [] arr4 = { 10 }; N = arr4.length; solve(N, arr4); print(arr4, N); } } // This code is contributed by sourabhdalal0001. |
Python3
# Python program for the above approach # Function performing calculation def solve( n, arr): temp = [ 0 ] * n; k = 0 ; vis = [ 0 ] * n; cur_or = 0 ; # Loop to calculate the maximum prefix x = min ( 30 ,n) for i in range (x, 0 , - 1 ): mx = 0 ; idx = - 1 ; for j in range (n): if vis[j]! = 0 : continue # If temp maximum element is # smaller than (previous or | current element) # then update temporary max if (mx < (cur_or | arr[j])): mx = (cur_or | arr[j]); idx = j; vis[idx] = 1 ; # Storing the element in the temp array temp[k] = arr[idx]; k = k + 1 ; cur_or = (cur_or | arr[idx]); for i in range (n): # Storing remaining element in the temp array if vis[i] = = 0 : temp[j] = arr[i]; j = j + 1 ; return temp; # Function for printing the array def printer(arr,n): for i in range (n): print (arr[i],end = " " ) print (); # Driver Code arr = [ 1 , 2 , 4 , 8 ]; N = len (arr); temp = solve(N, arr); printer(temp, N); arr2 = [ 1 , 2 ]; N = len (arr2); temp = solve(N, arr2); printer(temp, N); arr3 = [ 2 , 3 , 4 , 2 , 3 , 4 ]; N = len (arr3); temp = solve(N, arr3); printer(temp, N); arr4 = [ 10 ]; N = len (arr4); temp = solve(N, arr4); printer(temp, N); # This code is contributed by Potta Lokesh |
C#
// C# program for above approach using System; class GFG { // Function performing calculation static void solve( int n, int [] arr) { int [] temp = new int [n]; int j = 0; bool [] vis = new bool [n]; int cur_or = 0; // Loop to calculate the maximum prefix for ( int i = Math.Min(n, 30); i > 0; i--) { int mx = 0; int idx = -1; for ( int jj = 0; jj < n; jj++) { if (vis[jj]) continue ; // If temp maximum element is // smaller than (previous or | current element) // then update temporary max if (mx < (cur_or | arr[jj])) { mx = (cur_or | arr[jj]); idx = jj; } } vis[idx] = true ; // Storing the element in the temp array temp[j++] = arr[idx]; cur_or = (cur_or | arr[idx]); } for ( int i = 0; i < n; i++) { // Storing remaining element in the temp array if (!vis[i]) { temp[j++] = arr[i]; } } for ( int i=0;i<n;i++){ arr[i] = temp[i]; } } // Function for printing the array static void print( int [] arr, int n) { for ( int i = 0; i<n ; i++) { Console.Write(arr[i] + " " ); } Console.WriteLine(); } // Driver Code public static void Main() { int [] arr = { 1, 2, 4, 8 }; int N = arr.Length; solve(N, arr); print(arr, N); int [] arr2 = { 1, 2 }; N = arr2.Length; solve(N, arr2); print(arr2, N); int [] arr3 = { 2, 3, 4, 2, 3, 4 }; N = arr3.Length; solve(N, arr3); print(arr3, N); int [] arr4 = { 10 }; N = arr4.Length; solve(N, arr4); print(arr4, N); } } // This code is contributed by sanjoy_62. |
Javascript
// JS code to implement the approach // Function performing calculation function solve(n,arr) { let temp = Array(n); let j = 0; let vis = Array(n).fill( false ); let cur_or = 0; // Loop to calculate the maximum prefix for (let i = Math.min(n, 30); i > 0; i--) { let mx = 0; let idx = -1; for (let j = 0; j < n; j++) { if (vis[j]) continue ; // If temp maximum element is // smaller than (previous or | current element) // then update temporary max if (mx < (cur_or | arr[j])) { mx = (cur_or | arr[j]); idx = j; } } vis[idx] = true ; // Storing the element in the temp array temp[j++] = arr[idx]; cur_or = (cur_or | arr[idx]); } for (let i = 0; i < n; i++) { // Storing remaining element in the temp array if (!vis[i]) { temp[j++] = arr[i]; } } for (let i=0;i<n;i++){ arr[i] = temp[i]; } } // Function for printing the array function print(arr,n) { let line = "" ; for (let i = 0; i < n; i++) { line= line+ " " +(arr[i]); } console.log(line); } // Driver Code let arr = [ 1, 2, 4, 8 ]; let N = arr.length; solve(N, arr); print(arr, N); let arr2 = [ 1, 2 ]; N = arr2.length; solve(N, arr2); print(arr2, N); let arr3 = [ 2, 3, 4, 2, 3, 4 ]; N = arr3.length; solve(N, arr3); print(arr3, N); let arr4 = [10]; N = arr4.length; solve(N, arr3); print(arr4, N); // This code is contributed by ksam24000 |
8 4 2 1 2 1 4 3 2 10
Time Complexity: O(N * min(N, 30)) .
Auxiliary Space: O(N)
Related Articles:
Contact Us