Construya una array binaria lexicográficamente más pequeña de tamaño N con A 0 y conteo de inversión X

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: 

  1. 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.
  2. 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].
  3. 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.
  • 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)

Publicación traducida automáticamente

Artículo escrito por 64bit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *