Given three numbers N, A, and X, the task is to construct the lexicographically smallest binary array of size N, containing A 0s and having an inversion count of X.
Examples:
Input: N=5, A=2, X=1
Output: 0 1 0 1 1
Explanation:
The number of inversions in this array is 1(2nd and 3rd index).Input: N=5, A=2, X=3
Output: 0 1 1 1 0
Approach: The given problem can be solved using two pointer technique based on the following observations:
- The array with A 0s having 0 inversion is the array with all 0s to the beginning and then the all the 1s.
- If an element 0 at index i and an element 1 at index j is swapped, then inversion count increases by count of 1s in the range [i, j].
- The maximum possible inversion count is A*(N-A).
Follow the steps below to solve the problem:
- If X is greater than A*(N-A), print -1 and then return.
- Initialize an array say arr[] of size N and fill the first A Indices with 0s and the remaining with 1s.
- Initialize two variables curr as A-1 and prev as N-1 to iterate over the array.
- Iterate until X is greater than 0 and curr, is not less than 0, and perform the following steps:
- If X is greater than or equal prev-cur, then do the following:
- Swap the two elements at arr[prev], and arr[curr].
- Subtract prev-cur from X.
- Decrement prev and curr by 1.
- Otherwise, do the following:
- Swap the two elements arr[curr] and arr[cur+1].
- Increment curr by 1 and decrement X by 1.
- If X is greater than or equal prev-cur, then do the following:
- Print the array arr.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to construct lexicographically// smallest binary string of length N, having// A 0s and X inversionsvoid binaryArrayInversions(int N, int A, int X){ // If X inversions are not possible if (A * (N - A) < X) { cout << "-1"; return; } // Initialize array and fill with 0 int Arr[N] = { 0 }; // Fill last N-A indices with 1 fill(Arr + A, Arr + N, 1); // Stores the index of current 0 int cur = A - 1; // Stores the index of current 1 int prev = N - 1; // Iterate until X is greater than // 0 and cur is greater than equal // to 0 while (X && cur >= 0) { // If X is greater than or // equal to the prev-cur if (X >= prev - cur) { // Swap current 0 and current 1 swap(Arr[prev], Arr[cur]); // Update X X -= prev - cur; // Decrement prev and cur by 1 prev--; cur--; } // Otherwise else { // Swap current 0 with the next index swap(Arr[cur], Arr[cur + 1]); // Increment cur by 1 cur++; // Decrement X by 1 X--; } } // Print the array for (auto u : Arr) cout << u << " ";}// Driver codeint main(){ // Input int N = 5; int A = 2; int X = 1; // Function call binaryArrayInversions(N, A, X); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;class GFG{ // Function to construct lexicographically// smallest binary string of length N, having// A 0s and X inversionsstatic void binaryArrayInversions(int N, int A, int X){ // If X inversions are not possible if (A * (N - A) < X) { System.out.println("-1"); return; } // Initialize array and fill with 0 int []Arr = new int[N]; // Fill last N-A indices with 1 Arrays.fill(Arr, 0); for(int i = A; i < N; i++) Arr[i] = 1; // Stores the index of current 0 int cur = A - 1; // Stores the index of current 1 int prev = N - 1; // Iterate until X is greater than // 0 and cur is greater than equal // to 0 while (X != 0 && cur >= 0) { // If X is greater than or // equal to the prev-cur if (X >= prev - cur) { // Swap current 0 and current 1 int temp = Arr[prev]; Arr[prev] = Arr[cur]; Arr[cur] = temp; // Update X X -= prev - cur; // Decrement prev and cur by 1 prev--; cur--; } // Otherwise else { // Swap current 0 with the next index int temp = Arr[cur]; Arr[cur] = Arr[cur + 1]; Arr[cur + 1] = temp; // Increment cur by 1 cur++; // Decrement X by 1 X--; } } // Print the array for(int i = 0; i < Arr.length; i++) System.out.print(Arr[i] + " ");}// Driver codepublic static void main(String args[]){ // Input int N = 5; int A = 2; int X = 1; // Function call binaryArrayInversions(N, A, X);}}// This code is contributed by gfgking |
Python3
# Python3 program for the above approach# Function to construct lexicographically# smallest binary string of length N, having# A 0s and X inversionsdef binaryArrayInversions(N, A, X): # If X inversions are not possible if (A * (N - A) < X): print("-1") return # Initialize array and fill with 0 Arr = [0]*N for i in range(A,N): Arr[i]=1 # Stores the index of current 0 cur = A - 1 # Stores the index of current 1 prev = N - 1 # Iterate until X is greater than # 0 and cur is greater than equal # to 0 while (X and cur >= 0): # If X is greater than or # equal to the prev-cur if (X >= prev - cur): # Swap current 0 and current 1 Arr[prev], Arr[cur] = Arr[cur],Arr[prev] # Update X X -= prev - cur # Decrement prev and cur by 1 prev -= 1 cur -= 1 # Otherwise else: # Swap current 0 with the next index Arr[cur], Arr[cur + 1] = Arr[cur + 1], Arr[cur] # Increment cur by 1 cur += 1 # Decrement X by 1 X -= 1 # Print the array for u in Arr: print(u, end = " ")# Driver codeif __name__ == '__main__': # Input N = 5 A = 2 X = 1 # Function call binaryArrayInversions(N, A, X)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to construct lexicographically// smallest binary string of length N, having// A 0s and X inversionsstatic void binaryArrayInversions(int N, int A, int X){ // If X inversions are not possible if (A * (N - A) < X) { Console.Write("-1"); return; } // Initialize array and fill with 0 int []Arr = new int[N]; // Fill last N-A indices with 1 Array.Clear(Arr, 0, N); for(int i=A;i<N;i++) Arr[i] = 1; // Stores the index of current 0 int cur = A - 1; // Stores the index of current 1 int prev = N - 1; // Iterate until X is greater than // 0 and cur is greater than equal // to 0 while (X!=0 && cur >= 0) { // If X is greater than or // equal to the prev-cur if (X >= prev - cur) { // Swap current 0 and current 1 int temp = Arr[prev]; Arr[prev] = Arr[cur]; Arr[cur] = temp; // Update X X -= prev - cur; // Decrement prev and cur by 1 prev--; cur--; } // Otherwise else { // Swap current 0 with the next index int temp = Arr[cur]; Arr[cur] = Arr[cur + 1]; Arr[cur + 1] = temp; // Increment cur by 1 cur++; // Decrement X by 1 X--; } } // Print the array for(int i = 0; i < Arr.Length; i++) Console.Write(Arr[i] +" ");}// Driver codepublic static void Main(){ // Input int N = 5; int A = 2; int X = 1; // Function call binaryArrayInversions(N, A, X);}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script>// JavaScript program for the above approach// Function to construct lexicographically// smallest binary string of length N, having// A 0s and X inversionsfunction binaryArrayInversions(N, A, X) { // If X inversions are not possible if (A * (N - A) < X) { document.write("-1"); return; } // Initialize array and fill with 0 let Arr = new Array(N).fill(0); // Fill last N-A indices with 1 Arr.forEach((item, i) => { if (i >= Arr.length - (N - A)) { Arr[i] = 1 } }) // Stores the index of current 0 let cur = A - 1; // Stores the index of current 1 let prev = N - 1; // Iterate until X is greater than // 0 and cur is greater than equal // to 0 while (X && cur >= 0) { // If X is greater than or // equal to the prev-cur if (X >= prev - cur) { // Swap current 0 and current 1 let temp = Arr[prev]; Arr[prev] = Arr[cur]; Arr[cur] = temp; // Update X X -= prev - cur; // Decrement prev and cur by 1 prev--; cur--; } // Otherwise else { // Swap current 0 with the next index let temp = Arr[cur + 1]; Arr[cur + 1] = Arr[cur]; Arr[cur] = temp; // Increment cur by 1 cur++; // Decrement X by 1 X--; } } // Print the array document.write(Arr);}// Driver code// Inputlet N = 5;let A = 2;let X = 1;// Function callbinaryArrayInversions(N, A, X);</script> |
Output
0 1 0 1 1
Time complexity: O(N)
Auxiliary Space: O(1)
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!
