Rearrange given Array such that all set bit positions have higher value than others
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++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to do required
// operation
void 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 Code
int 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 program for the above approach
import java.io.*;
import java.util.*;
// User defined Pair class
class Pair {
int x;
int y;
// Constructor
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// class to define user defined conparator
class 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 program for the above approach
# Function to do required operation
def 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 Code
N = 3
b1 = [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# program to implement above approach
using 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__
<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)
Customized Sorting and Placement Strategy Based on Flag Array
The approach described here is utilized to reorder an array B1 in a manner dictated by a corresponding flag array B2. Elements in B1 are rearranged such that those associated with a ‘1’ in B2 are placed first, sorted in descending order, and those associated with a ‘0’ are sorted in ascending order and placed afterwards. This method is particularly effective when you need to prioritize certain elements based on binary conditions while maintaining an ordered sequence within those priorities. It is suitable for applications where dynamic reordering is necessary based on external or updated criteria, such as in task scheduling, prioritizing resources, or data processing tasks where order affects output quality or processing efficiency.
Follow the steps to solve the problem:
- Generate lists of indices where bits are set and unset in B2.
- Separate B1 values into two groups based on the bit values in B2.
- Sort the values where bits are set in descending order and where bits are unset in ascending order.
- Reinsert the sorted values back into their respective positions in B1 according to the layout specified by B2.
Below is the implementation of above approach:
#include <algorithm>
#include <iostream>
#include <vector>
// Function to rearrange elements in b1 according to the bit
// values in b2
void rearrange_array(std::vector<int>& b1,
std::vector<int>& b2)
{
// Check if the sizes of b1 and b2 are the same
if (b1.size() != b2.size()) {
std::cerr << "Error: Arrays b1 and b2 must be of "
"the same size."
<< std::endl;
return;
}
// Vectors to store indices of set and unset bits in b2
std::vector<int> indices_with_set_bits;
std::vector<int> indices_with_unset_bits;
// Loop through b2 to categorize indices based on bit
// value
for (int i = 0; i < b2.size(); i++) {
if (b2[i] == 1)
indices_with_set_bits.push_back(i);
else if (b2[i] == 0)
indices_with_unset_bits.push_back(i);
}
// Vectors to hold the values from b1 corresponding to
// the categorized indices
std::vector<int> values_with_set_bits;
std::vector<int> values_with_unset_bits;
// Extract values from b1 based on the indices of set
// and unset bits
for (int index : indices_with_set_bits)
values_with_set_bits.push_back(b1[index]);
for (int index : indices_with_unset_bits)
values_with_unset_bits.push_back(b1[index]);
// Sorting values with set bits in descending order
std::sort(values_with_set_bits.begin(),
values_with_set_bits.end(),
std::greater<int>());
// Sorting values with unset bits in ascending order
std::sort(values_with_unset_bits.begin(),
values_with_unset_bits.end());
// Reinserting the sorted values back into b1 based on
// the original bit positions
for (int i = 0; i < indices_with_set_bits.size(); i++)
b1[indices_with_set_bits[i]]
= values_with_set_bits[i];
for (int i = 0; i < indices_with_unset_bits.size(); i++)
b1[indices_with_unset_bits[i]]
= values_with_unset_bits[i];
}
int main()
{
// Example arrays
std::vector<int> B1 = { 3, 4, 5 };
std::vector<int> B2 = { 1, 1, 1 };
// Calling the function to rearrange B1 according to B2
rearrange_array(B1, B2);
// Output the rearranged array
for (int i : B1)
std::cout << i << " ";
return 0;
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
// Function to rearrange elements in b1 according to the
// bit values in b2
static void rearrangeArray(List<Integer> b1,
List<Integer> b2)
{
// Check if the sizes of b1 and b2 are the same
if (b1.size() != b2.size()) {
System.err.println(
"Error: Arrays b1 and b2 must be of the same size.");
return;
}
// Lists to store indices of set and unset bits in
// b2
List<Integer> indicesWithSetBits
= new ArrayList<>();
List<Integer> indicesWithUnsetBits
= new ArrayList<>();
// Loop through b2 to categorize indices based on
// bit value
for (int i = 0; i < b2.size(); i++) {
if (b2.get(i) == 1) {
indicesWithSetBits.add(i);
}
else if (b2.get(i) == 0) {
indicesWithUnsetBits.add(i);
}
}
// Lists to hold the values from b1 corresponding to
// the categorized indices
List<Integer> valuesWithSetBits = new ArrayList<>();
List<Integer> valuesWithUnsetBits
= new ArrayList<>();
// Extract values from b1 based on the indices of
// set and unset bits
for (int index : indicesWithSetBits) {
valuesWithSetBits.add(b1.get(index));
}
for (int index : indicesWithUnsetBits) {
valuesWithUnsetBits.add(b1.get(index));
}
// Sorting values with set bits in descending order
Collections.sort(valuesWithSetBits,
Collections.reverseOrder());
// Sorting values with unset bits in ascending order
Collections.sort(valuesWithUnsetBits);
// Reinserting the sorted values back into b1 based
// on the original bit positions
for (int i = 0; i < indicesWithSetBits.size();
i++) {
b1.set(indicesWithSetBits.get(i),
valuesWithSetBits.get(i));
}
for (int i = 0; i < indicesWithUnsetBits.size();
i++) {
b1.set(indicesWithUnsetBits.get(i),
valuesWithUnsetBits.get(i));
}
}
public static void main(String[] args)
{
// Example arrays
List<Integer> B1 = new ArrayList<>();
Collections.addAll(B1, 3, 4, 5);
List<Integer> B2 = new ArrayList<>();
Collections.addAll(B2, 1, 1, 1);
// Calling the function to rearrange B1 according to
// B2
rearrangeArray(B1, B2);
// Output the rearranged array
for (int i : B1) {
System.out.print(i + " ");
}
}
}
def rearrange_array(b1, b2):
# Identifying the indices where bits are set and unset
indices_with_set_bits = [i for i in range(len(b2)) if b2[i] == 1]
indices_with_unset_bits = [i for i in range(len(b2)) if b2[i] == 0]
# Extracting values based on the bit status for sorting
values_with_set_bits = [b1[i] for i in indices_with_set_bits]
values_with_unset_bits = [b1[i] for i in indices_with_unset_bits]
# Sorting in descending order for 'set bits' and ascending for 'unset bits'
values_with_set_bits.sort(reverse=True)
values_with_unset_bits.sort()
# Reinserting sorted values back into the original array according to original bit positions
for i, index in enumerate(indices_with_set_bits):
b1[index] = values_with_set_bits[i]
for i, index in enumerate(indices_with_unset_bits):
b1[index] = values_with_unset_bits[i]
return b1
# Using the function to rearrange arrays
B1 = [3, 4, 5]
B2 = [1, 1, 1]
# Output should be [5, 4, 3] due to descending order sort of all set bits
ans = rearrange_array(B1, B2)
for i in ans:
print(i, end=" ")
function rearrangeArray(b1, b2) {
// Check if the sizes of b1 and b2 are the same
if (b1.length !== b2.length) {
console.error("Error: Arrays b1 and b2 must be of the same size.");
return;
}
// Arrays to store indices of set and unset bits in b2
const indicesWithSetBits = [];
const indicesWithUnsetBits = [];
// Loop through b2 to categorize indices based on bit value
b2.forEach((bit, index) => {
if (bit === 1) {
indicesWithSetBits.push(index);
} else if (bit === 0) {
indicesWithUnsetBits.push(index);
}
});
// Arrays to hold the values from b1 corresponding to the categorized indices
const valuesWithSetBits = [];
const valuesWithUnsetBits = [];
// Extract values from b1 based on the indices of set and unset bits
indicesWithSetBits.forEach(index => {
valuesWithSetBits.push(b1[index]);
});
indicesWithUnsetBits.forEach(index => {
valuesWithUnsetBits.push(b1[index]);
});
// Sorting values with set bits in descending order
valuesWithSetBits.sort((a, b) => b - a);
// Sorting values with unset bits in ascending order
valuesWithUnsetBits.sort((a, b) => a - b);
// Reinserting the sorted values back into b1 based on the original bit positions
indicesWithSetBits.forEach((index, i) => {
b1[index] = valuesWithSetBits[i];
});
indicesWithUnsetBits.forEach((index, i) => {
b1[index] = valuesWithUnsetBits[i];
});
}
// Example arrays
const B1 = [3, 4, 5];
const B2 = [1, 1, 1];
// Calling the function to rearrange B1 according to B2
rearrangeArray(B1, B2);
// Output the rearranged array
console.log(B1.join(" "));
Output
5 4 3
Time Complexity: O(NlogN)
Auxilary Space: O(N)
Contact Us