Dados tres números N , A y X , la tarea es construir la array binaria lexicográficamente más pequeña de tamaño N , que contenga A 0 s y tenga un recuento de inversión de X .
Ejemplos:
Entrada: N=5, A=2, X=1
Salida: 0 1 0 1 1
Explicación:
El número de inversiones en esta array es 1 (segundo y tercer índice).Entrada: N=5, A=2, X=3
Salida: 0 1 1 1 0
Enfoque: El problema dado se puede resolver usando la técnica de dos punteros basada en las siguientes observaciones:
- La array con A 0 s que tiene inversión 0 es la array con todos los 0 al principio y luego todos los 1 s.
- Si se intercambia un elemento 0 en el índice i y un elemento 1 en el índice j , entonces el conteo de inversión aumenta en 1 s en el rango [i, j].
- La cuenta de inversión máxima posible es A*(NA).
Siga los pasos a continuación para resolver el problema:
- Si X es mayor que A*(NA) , imprima -1 y luego regrese.
- Inicialice una array, digamos arr[] de tamaño N y complete los primeros índices A con 0 s y el resto con 1 s.
- Inicialice dos variables curr como A-1 y prev como N-1 para iterar sobre la array .
- Itere hasta que X sea mayor que 0 y curr , no sea menor que 0 , y realice los siguientes pasos:
- Si X es mayor o igual que prev-cur , haga lo siguiente:
- Intercambie los dos elementos en arr[prev] y arr[curr].
- Reste prev-cur de X .
- Decrementar prev y curr en 1.
- De lo contrario, haga lo siguiente:
- Intercambia los dos elementos arr[curr] y arr[cur+1] .
- Incremente curr en 1 y disminuya X en 1.
- Si X es mayor o igual que prev-cur , haga lo siguiente:
- Imprima la array arr.
A continuación se muestra la implementación del enfoque anterior:
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 inversions void 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 code int 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 approach import java.util.Arrays; class GFG{ // Function to construct lexicographically // smallest binary string of length N, having // A 0s and X inversions static 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 code public 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 inversions def 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 code if __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 approach using System; using System.Collections.Generic; class GFG { // Function to construct lexicographically // smallest binary string of length N, having // A 0s and X inversions static 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 code public 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 inversions function 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 // Input let N = 5; let A = 2; let X = 1; // Function call binaryArrayInversions(N, A, X); </script>
Producción
0 1 0 1 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)