Número mínimo de pasos requeridos para colocar todos los 1 en un solo índice

Dada una array binaria A[] de tamaño N , donde todos los 1 se pueden mover a su posición adyacente, la tarea es imprimir una array res[] de tamaño N , donde res[i] contiene el número mínimo de pasos necesarios para mover todos los 1 s en el i ^-ésimo índice.

Ejemplos:

Entrada: A[] = {1, 0, 1, 0}
Salida: {2, 2, 2, 4}
Explicación: 
Para i = 0, mover todos los 1 al índice 0 ^requiere 2 pasos, es decir, abs (0 – 0 ) + abs(0 – 2) = 2.
Para i = 1, mover todos los 1 al ^1er índice requiere 2 pasos, es decir, abs(1 – 0) + abs(1 – 2) = 2.
Para i = 2, mover todos los 1 al 2 ^° índice requieren 2 pasos, es decir abs(2 – 0) + abs(2 – 2) = 2.
Para i = 3, mover todos los 1 al 3 ^° índice requiere 4 pasos, es decir abs(3 – 0) + abs(3 – 2) = 4.
Por lo tanto, res[] es {2, 2, 2, 4}

Entrada: A[] = {0, 0, 1, 0, 0, 1}
Salida: {7, 5, 3, 3, 3, 3}
Explicación:
Para i = 0, mover todos los 1 al ^0º índice requiere 7 pasos, es decir, abs(2 – 0) + abs(5 – 0) = 7.
Para i = 1, mover todos los 1 al ^1er índice requiere 5 pasos, es decir, abs(2 – 1) + abs(5 – 1) = 5.
Para i = 2, mover todos los 1 al 2. ^° índice requiere 3 pasos, es decir, abs(2 – 2) + abs(5 – 2) = 3.
Para i = 3, mover todos los 1 al 3.er índice requerirá 3 pasos , es decir, abs(2 – 2) + abs(5 – 3) = 3.
Para i = 4, mover todos los 1 al ^4º índice tomará 3 pasos, es decir, abs(2 – 4) + abs(5 – 4) = 3.
Para i = 5, moviendo todos los 1 al ⁵index tomará 3 pasos, es decir, abs(2 – 5) + abs(5 – 5) = 3.
Por lo tanto, res[] es {7, 5, 3, 3, 3, 3}
 

Enfoque ingenuo : siga los pasos para resolver el problema:

1. Atraviesa la array .
2. Para cada i ^-ésimo índice, cuente el número de pasos necesarios para mover todos los 1 al i ^-ésimo índice.
3. Iterar sobre el rango [0, N – 1] , usando una variable, digamos i.
   • Inicializar pasos = 0.
   • Iterar sobre el rango [0, N – 1] , usando una variable j.
   • Si A[j] es igual a 1, agregue abs(i – j) a los pasos.
4. Imprime el número mínimo de pasos .

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1 )

Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar Prefix Sum . Siga los pasos a continuación para resolver este problema:

1. Atraviesa la array .
2. Inicialice una array, diga left[] e inicialice count = A[0].
3. Iterar sobre el rango [1, N – 1] y actualizar left[i] = left[i – 1] + count , donde count es el número de 1 s en el lado izquierdo de i.
4. Inicialice una array, diga right[] e inicialice count = A[N – 1].
5. Itere sobre el rango [N – 2, 0] y actualice right[i] = right[i + 1] + count , donde count es el número de 1 s en el lado derecho de i.
6. Calcule y actualice la respuesta final en res[] , donde res[i] es la suma de los pasos de los lados izquierdo y derecho, es decir, res[i] = derecha[i] + izquierda[i]
7. Imprime la array res[] .

 A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print minimum steps
// required to shift all 1s to a
// single index in a binary array
void minsteps(vector<int>& A)
{
    // Size of array
    int n = A.size();
 
    // Used to store cumulative sum
    vector<int> left(n, 0), right(n, 0), res(n, 0);
 
    // Initialize count
    int count = A[0];
 
    // Traverse the array in
    // forward direction
    for (int i = 1; i < n; i++) {
        // Steps needed to store all
        // previous ones to ith index
        left[i] = left[i - 1] + count;
 
        // Count number of 1s
        // present till i-th index
        count += A[i];
    }
 
    // Initialize count
    count = A[n - 1];
 
    // Traverse the array in
    // backward direction
    for (int i = n - 2; i >= 0; i--) {
        // Steps needed to store all 1s to
        // the right of i at current index
        right[i] = right[i + 1] + count;
 
        // Count number of 1s
        // present after i-th index
        count += A[i];
    }
 
    // Print the number of steps required
    for (int i = 0; i < n; i++) {
        res[i] = left[i] + right[i];
        cout << res[i] << " ";
    }
    cout << "\n";
}
 
// Driver Code
int main()
{
    vector<int> A = { 1, 0, 1, 0 };
    minsteps(A);
}

// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG
{
 
  // Function to print minimum steps
  // required to shift all 1s to a
  // single index in a binary array
  static void minsteps(int[] A)
  {
     
    // Size of array
    int n = A.length;
 
    // Used to store cumulative sum
    int[] left = new int [n];
    Arrays.fill(left, 0);
    int[] right = new int [n];
    Arrays.fill(right, 0);
    int[] res = new int [n];
    Arrays.fill(res, 0);
 
    // Initialize count
    int count = A[0];
 
    // Traverse the array in
    // forward direction
    for (int i = 1; i < n; i++) {
      // Steps needed to store all
      // previous ones to ith index
      left[i] = left[i - 1] + count;
 
      // Count number of 1s
      // present till i-th index
      count += A[i];
    }
 
    // Initialize count
    count = A[n - 1];
 
    // Traverse the array in
    // backward direction
    for (int i = n - 2; i >= 0; i--) {
      // Steps needed to store all 1s to
      // the right of i at current index
      right[i] = right[i + 1] + count;
 
      // Count number of 1s
      // present after i-th index
      count += A[i];
    }
 
    // Print the number of steps required
    for (int i = 0; i < n; i++) {
      res[i] = left[i] + right[i];
      System.out.print(res[i] + " ");
    }
    System.out.println();
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int[] A = { 1, 0, 1, 0 };
    minsteps(A);
  }
}
 
// This code is contributed by souravghosh0416.

# Python3 implementation of
# the above approach
 
# Function to print minimum steps
# required to shift all 1s to a
# single index in a binary array
def minsteps(A):
   
    # Size of array
    n = len(A)
 
    # Used to store cumulative sum
    left, right, res =[0]*n, [0]*n, [0]*n
 
    # Initialize count
    count = A[0]
 
    # Traverse the array in
    # forward direction
    for i in range(1, n):
       
        # Steps needed to store all
        # previous ones to ith index
        left[i] = left[i - 1] + count
 
        # Count number of 1s
        # present till i-th index
        count += A[i]
 
    # Initialize count
    count = A[n - 1]
 
    # Traverse the array in
    # backward direction
    for i in range(n - 2, -1, -1):
       
        # Steps needed to store all 1s to
        # the right of i at current index
        right[i] = right[i + 1] + count
 
        # Count number of 1s
        # present after i-th index
        count += A[i]
 
    # Print the number of steps required
    for i in range(n):
        res[i] = left[i] + right[i]
        print(res[i], end = " ")
    print()
 
# Driver Code
if __name__ == '__main__':
    A = [1, 0, 1, 0]
    minsteps(A)
 
# This code is contributed by mohit kumar 29.

// C# Program to implement
// the above approach
using System;
class GFG
{
   
  // Function to print minimum steps
  // required to shift all 1s to a
  // single index in a binary array
  static void minsteps(int[] A)
  {
 
    // Size of array
    int n = A.Length;
 
    // Used to store cumulative sum
    int[] left = new int [n];
    for (int i = 1; i < n; i++) {
      left[i] = 0;
    }
 
    int[] right = new int [n];
    for (int i = 1; i < n; i++) {
      right[i] = 0;
    }
 
    int[] res = new int [n];
    for (int i = 1; i < n; i++) {
      res[i] = 0;
    }
 
    // Initialize count
    int count = A[0];
 
    // Traverse the array in
    // forward direction
    for (int i = 1; i < n; i++) {
      // Steps needed to store all
      // previous ones to ith index
      left[i] = left[i - 1] + count;
 
      // Count number of 1s
      // present till i-th index
      count += A[i];
    }
 
    // Initialize count
    count = A[n - 1];
 
    // Traverse the array in
    // backward direction
    for (int i = n - 2; i >= 0; i--) {
      // Steps needed to store all 1s to
      // the right of i at current index
      right[i] = right[i + 1] + count;
 
      // Count number of 1s
      // present after i-th index
      count += A[i];
    }
 
    // Print the number of steps required
    for (int i = 0; i < n; i++) {
      res[i] = left[i] + right[i];
      Console.Write(res[i] + " ");
    }
    Console.WriteLine();
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[] A = { 1, 0, 1, 0 };
    minsteps(A);
  }
}
 
// This code is contributed by susmitakundugoaldanga.

<script>
 
// JavaScript program to implement
// the above approach
 
  // Function to print minimum steps
  // required to shift all 1s to a
  // single index in a binary array
  function minsteps(A)
  {
      
    // Size of array
    let n = A.length;
  
    // Used to store cumulative sum
    let left = Array.from({length: n}, (_, i) => 0);
    let right = Array.from({length: n}, (_, i) => 0);
    let res = Array.from({length: n}, (_, i) => 0);
  
    // Initialize count
    let count = A[0];
  
    // Traverse the array in
    // forward direction
    for (let i = 1; i < n; i++) {
      // Steps needed to store all
      // previous ones to ith index
      left[i] = left[i - 1] + count;
  
      // Count number of 1s
      // present till i-th index
      count += A[i];
    }
  
    // Initialize count
    count = A[n - 1];
  
    // Traverse the array in
    // backward direction
    for (let i = n - 2; i >= 0; i--) {
      // Steps needed to store all 1s to
      // the right of i at current index
      right[i] = right[i + 1] + count;
  
      // Count number of 1s
      // present after i-th index
      count += A[i];
    }
  
    // Print the number of steps required
    for (let i = 0; i < n; i++) {
      res[i] = left[i] + right[i];
      document.write(res[i] + " ");
    }
    document.write("<br/>");
  }
 
// Driver code   
    let A = [ 1, 0, 1, 0 ];
    minsteps(A);
 
// This code is contributed by sanjoy_62.
</script>

2 2 2 4

Complejidad temporal: O(N)
Espacio auxiliar: O(N)