Given an array B1[] and a binary array B2[] each of size N, the task is to rearrange array B1[] in a way such that for all setbit position i of B2[] the value of B1[i] will be greater than the values where bit is not set in B2[] i.e for all (i, j) B1[i] > B1[j] when B2[i] = 1, B2[j] = 0 (0 ≤ i, j < N).
Note: If multiple arrangements are possible, print any one of them.
Examples:
Input: N = 7, B1[] = {1, 2, 3, 4, 5, 6, 7}, B2[] = {0, 1, 0, 1, 0, 1, 0}
Output: 1 5 2 6 3 7 4
Explanation: Values having 1 in B2[] array are = {2, 4, 6} and values with 0s are = {1, 3, 5, 7}.
So, in correspondent to B2[] array, B1[] can be rearranged = {1, 5, 2, 6, 3, 7, 4}
B1[] = {1, 5, 2, 6, 3, 7, 4}
B2[] = {0, 1, 0, 1, 0, 1, 0}, now all places in B1[i] > B1[j] where B2[i] = 1, and B2[j] = 0.
It also can be rearranged as {1, 7, 2, 6, 3, 5, 4}Input: N = 3, B1[] = {4, 3, 5}, B2[] = {1, 1, 1}
Output: 5 4 3
Approach: The problem can be solved based on the following idea:
To arrange B1[] as per set bit positions of B2[], sort the values of B1[] and arrange the higher values in positions with bits set and the lower values in positions in other positions.
Follow the steps mentioned below to implement the above idea:
- Make a list of pairs (say v) with the bit value of B2[] and the corresponding value at B1[],
- Sort the list of pairs in ascending order of bits value of B2[].
- Rearrange B1[] using two pointer approach.
- Declare left pointer with 0 and right pointer with N-1.
- When B2[i] is 0 (0 ≤ i < N), set B1[] as v[left] and increment left.
- Otherwise, set B1[i] as v[right] and decrement right.
- Return B1[] as the final answer.
Below is the implementation of the above approach :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to do required// operationvoid solve(int n, vector<int>& b1, int b2[]){ // Initializing vector of pair // to store b2 and b1 array element vector<pair<int, int> > v; int cnt = 1; for (int i = 0; i < n; i++) { // Pushing 1 and 0 integer along with // their corresponding element // in array b1 v.push_back({ b2[i], b1[i] }); } // Sorting the vector of pair // in ascending order sort(v.begin(), v.end()); int left = 0, right = n - 1; // Arranging the array b1 for (int i = 0; i < n; i++) { if (b2[i] == 0) b1[i] = v[left++].second; else b1[i] = v[right--].second; }}// Driver Codeint main(){ int N = 3; vector<int> B1 = { 3, 4, 5 }; int B2[] = { 1, 1, 1 }; solve(N, B1, B2); for (int x : B1) cout << x << " "; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;// User defined Pair classclass Pair { int x; int y; // Constructor public Pair(int x, int y) { this.x = x; this.y = y; }}// class to define user defined conparatorclass Compare { static void compare(Pair arr[], int n) { // Comparator to sort the pair according to second element Arrays.sort(arr, new Comparator<Pair>() { @Override public int compare(Pair p1, Pair p2) { return p1.x - p2.x; // To compare the first element just //change the variable from p1.y - p2.y to x. } }); }}class GFG { // Function to do required // operation static void solve(int n, int[] b1, int[] b2) { // Initializing vector of pair // to store b2 and b1 array element // Array of Pair Pair v[] = new Pair[n]; int cnt = 1; for (int i = 0; i < n; i++) { // Pushing 1 and 0 integer along with // their corresponding element // in array b1 v[i] = new Pair(b2[i], b1[i]); } // Sorting the vector of pair // in ascending order Compare obj = new Compare(); obj.compare(v, n); int left = 0, right = n - 1; // Arranging the array b1 for (int i = 0; i < n; i++) { if (b2[i] == 0) b1[i] = v[left++].y; else b1[i] = v[right--].y; } } // Driver Code public static void main (String[] args) { int N = 3; int B1[] = { 3, 4, 5 }; int B2[] = { 1, 1, 1 }; solve(N, B1, B2); for (int i = 0; i <B1.length; i++) System.out.print(B1[i] + " "); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python3 program for the above approach# Function to do required operationdef solve(n, b1, b2): # Initializing list of pair to store b2 and b1 array element v = [] cnt = 1 for i in range(n): # Pushing 1 and 0 integer along with # their corresponding element in array b1 v.append([b2[i], b1[i]]) v.sort() left = 0 right = n - 1 # Arranging the array b1 for i in range(n): if b2[i] == 0: b1[i] = v[left][1] left += 1 else: b1[i] = v[right][1] right -= 1 # Driver CodeN = 3b1 = [3, 4, 5]b2 = [1, 1, 1]solve(N, b1, b2)for x in b1: print(x, end = " ")''' This code is written by Rajat Kumar (GLA University)''' |
C#
// C# program to implement above approachusing System;using System.Collections.Generic;public class GFG{ class pair : IComparable<pair> { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } public int CompareTo(pair b) { if (this.first != b.first) return (this.first < b.first)?-1:1; else return this.second > b.second?-1:1; } } static void solve(int n, int[] b1, int[] b2) { List<pair > v = new List<pair > (); for (int i = 0; i < n; i++) { // Pushing 1 and 0 integer along with // their corresponding element // in array b1 v.Add(new pair(b2[i], b1[i])); } // Sorting the vector of pair // in ascending order v.Sort(); int left = 0, right = n - 1; // Arranging the array b1 for (int i = 0; i < n; i++) { if (b2[i] == 0) b1[i] = v[left++].second; else b1[i] = v[right--].second; } } public static void Main (){ // Code int N = 3; int[] B1 = { 3, 4, 5 }; int[] B2 = { 1, 1, 1 }; solve(N, B1, B2); for (int i = B1.Length-1; i >=0 ; i--) { Console.Write(B1[i]); Console.Write(" "); } }}// This code is contributed by akashish__ |
Javascript
<script> // JavaScript program for the above approach // Function to do required // operation const solve = (n, b1, b2) => { // Initializing vector of pair // to store b2 and b1 array element let v = []; let cnt = 1; for (let i = 0; i < n; i++) { // Pushing 1 and 0 integer along with // their corresponding element // in array b1 v.push([b2[i], b1[i]]); } // Sorting the vector of pair // in ascending order v.sort(); let left = 0, right = n - 1; // Arranging the array b1 for (let i = 0; i < n; i++) { if (b2[i] == 0) b1[i] = v[left++][1]; else b1[i] = v[right--][1]; } } // Driver Code let N = 3; let B1 = [3, 4, 5]; let B2 = [1, 1, 1]; solve(N, B1, B2); for (let x in B1) document.write(`${B1[x]} `); // This code is contributed by rakeshsahni</script> |
Output
5 4 3
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
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!
Share your thoughts in the comments
