Dada una array binaria , en la que mover un elemento del índice i al índice j requiere un costo abs(i – j) . La tarea es encontrar el costo de mover todos los 1 a cada índice de la array dada.
Ejemplos:
Entrada: arr[] = {0, 1, 0, 1}
Salida : 4 2 2 2
Explicación:
Mover elementos del índice 1, índice 3 al índice 0 requiere abs(0 – 1) + abs(0 – 3) = 4 Mover elementos del
índice 1, índice 3 al índice 1 requiere abs(1 – 1) + abs(1 – 3) = 2.
Mover elementos del índice 1, índice 2 al índice 2 requiere abs(2 – 1) + abs( 2 – 3) = 2.
Mover elementos del índice 1, índice 2 al índice 3 requiere abs(3 – 1) + abs(3 – 3) = 2.
Por lo tanto, la salida requerida es 4 2 2 2.Entrada: arr[] = {1, 1, 1}
Salida: 3 2 3
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array dada y, para cada elemento de array de la array dada, imprimir el costo de mover todos los 1 s de la array dada al índice actual.
A continuación se muestran las implementaciones del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the cost
// to move all 1s to each index
void costMove1s(int arr[], int N)
{
// Traverse the array.
for (int i = 0; i < N; i++) {
// Stores cost to move
// all 1s at current index
int cost = 0;
// Calculate cost to move
// all 1s at current index
for (int j = 0; j < N;
j++) {
// If current element
// of the array is 1.
if (arr[j] == 1) {
// Update cost
cost += abs(i - j);
}
}
cout<<cost<<" ";
}
}
// Driver Code
int main()
{
int arr[] = { 0, 1, 0, 1};
int N = sizeof(arr) / sizeof(arr[0]);
costMove1s(arr, N);
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to print the cost
// to move all 1s to each index
static void costMove1s(int[] arr, int N)
{
// Traverse the array.
for(int i = 0; i < N; i++)
{
// Stores cost to move
// all 1s at current index
int cost = 0;
// Calculate cost to move
// all 1s at current index
for(int j = 0; j < N; j++)
{
// If current element
// of the array is 1.
if (arr[j] == 1)
{
// Update cost
cost += Math.abs(i - j);
}
}
System.out.print(cost + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 0, 1, 0, 1 };
int N = arr.length;
costMove1s(arr, N);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program to implement # the above approach # Function to print the cost # to move all 1s to each index def costMove1s(arr, N): # Traverse the array. for i in range(0, N): # Stores cost to move # all 1s at current index cost = 0 # Calculate cost to move # all 1s at current index for j in range(0, N): # If current element # of the array is 1. if (arr[j] == 1): # Update cost cost = cost + abs(i - j) print(cost, end = " ") # Driver Code if __name__ == "__main__": arr = [ 0, 1, 0, 1 ] N = len(arr) costMove1s(arr, N) # This code is contributed by akhilsaini
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to print the cost
// to move all 1s to each index
static void costMove1s(int[] arr, int N)
{
// Traverse the array.
for(int i = 0; i < N; i++)
{
// Stores cost to move
// all 1s at current index
int cost = 0;
// Calculate cost to move
// all 1s at current index
for(int j = 0; j < N; j++)
{
// If current element
// of the array is 1.
if (arr[j] == 1)
{
// Update cost
cost += Math.Abs(i - j);
}
}
Console.Write(cost + " ");
}
}
// Driver Code
public static void Main()
{
int[] arr = { 0, 1, 0, 1 };
int N = arr.Length;
costMove1s(arr, N);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to print the cost
// to move all 1s to each index
function costMove1s(arr, N)
{
// Traverse the array.
for (let i = 0; i < N; i++) {
// Stores cost to move
// all 1s at current index
let cost = 0;
// Calculate cost to move
// all 1s at current index
for (let j = 0; j < N;
j++) {
// If current element
// of the array is 1.
if (arr[j] == 1) {
// Update cost
cost += Math.abs(i - j);
}
}
document.write(cost + " ");
}
}
// Driver Code
let arr = [ 0, 1, 0, 1];
let N = arr.length;
costMove1s(arr, N);
//This code is contributed by Mayank Tyagi
</script>
Producción:
4 2 2 2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es atravesar la array dada y encontrar el costo de mover todos los 1 desde el lado izquierdo y derecho de cada índice de la array dada utilizando la técnica de suma de prefijos . Siga los pasos a continuación para resolver el problema:
- Inicialice una array, diga cost[] para almacenar el costo de mover todos los 1 en cada índice de la array dada.
- Inicialice dos variables, digamos costLeft , costRight para almacenar el costo de mover todos los 1 desde el lado izquierdo y derecho de cada índice respectivamente.
- Recorra la array dada de izquierda a derecha e incremente el valor de costLeft por el número de 1 s en el lado izquierdo y el valor de result[i] por costLeft ..
- Recorra la array dada de derecha a izquierda e incremente el valor de costRight por el número de 1 s en el lado derecho y el valor de result[i] por costRight .
- Finalmente, imprima la array cost[] .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the cost
// to move all 1s to each index
void costMove1s(int arr[], int N)
{
// cost[i] Stores cost to move
// all 1s at index i
int cost[N] = { 0 };
// Stores count of 1s on
// the left side of index i
int cntLeft = 0;
// Stores cost to move all 1s
// from the left side of index i
// to index i
int costLeft = 0;
// Traverse the array from
// left to right.
for (int i = 0; i < N; i++) {
// Update cost to move
// all 1s from left side
// of index i to index i
costLeft += cntLeft;
// Update cost[i] to cntLeft
cost[i] += costLeft;
// If current element is 1.
if (arr[i] == 1) {
cntLeft++;
}
}
// Stores count of 1s on
// the right side of index i
int cntRight = 0;
// Stores cost to move all 1s
// from the right of index i
// to index i
int costRight = 0;
// Traverse the array from
// right to left.
for (int i = N - 1; i >= 0;
i--) {
// Update cost to move
// all 1s from right side
// of index i to index i
costRight += cntRight;
// Update cost[i]
// to costRight
cost[i] += costRight;
// If current element
// is 1.
if (arr[i] == 1) {
cntRight++;
}
}
// Print cost to move all 1s
for(int i = 0; i< N; i++) {
cout<<cost[i]<<" ";
}
}
// Driver Code
int main()
{
int arr[] = { 0, 1, 0, 1};
int N = sizeof(arr) / sizeof(arr[0]);
costMove1s(arr, N);
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to print the cost
// to move all 1s to each index
static void costMove1s(int arr[], int N)
{
// cost[i] Stores cost to move
// all 1s at index i
int cost[] = new int[N];
// Stores count of 1s on
// the left side of index i
int cntLeft = 0;
// Stores cost to move all 1s
// from the left side of index i
// to index i
int costLeft = 0;
// Traverse the array from
// left to right.
for(int i = 0; i < N; i++)
{
// Update cost to move
// all 1s from left side
// of index i to index i
costLeft += cntLeft;
// Update cost[i] to cntLeft
cost[i] += costLeft;
// If current element is 1.
if (arr[i] == 1)
{
cntLeft++;
}
}
// Stores count of 1s on
// the right side of index i
int cntRight = 0;
// Stores cost to move all 1s
// from the right of index i
// to index i
int costRight = 0;
// Traverse the array from
// right to left.
for(int i = N - 1; i >= 0; i--)
{
// Update cost to move
// all 1s from right side
// of index i to index i
costRight += cntRight;
// Update cost[i]
// to costRight
cost[i] += costRight;
// If current element
// is 1.
if (arr[i] == 1)
{
cntRight++;
}
}
// Print cost to move all 1s
for(int i = 0; i < N; i++)
{
System.out.print(cost[i] + " ");
}
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 0, 1, 0, 1 };
int N = arr.length;
// Function Call
costMove1s(arr, N);
}
}
// This code is contributed by math_lover
Python3
# Python3 program to implement # the above approach # Function to print the cost # to move all 1s to each index def costMove1s(arr, N): # cost[i] Stores cost to move # all 1s at index i cost = [0] * N # Stores count of 1s on # the left side of index i cntLeft = 0 # Stores cost to move all 1s # from the left side of index i # to index i costLeft = 0 # Traverse the array from # left to right. for i in range(N): # Update cost to move # all 1s from left side # of index i to index i costLeft += cntLeft # Update cost[i] to cntLeft cost[i] += costLeft # If current element is 1. if (arr[i] == 1): cntLeft += 1 # Stores count of 1s on # the right side of index i cntRight = 0 # Stores cost to move all 1s # from the right of index i # to index i costRight = 0 # Traverse the array from # right to left. for i in range(N - 1, -1, -1): # Update cost to move # all 1s from right side # of index i to index i costRight += cntRight # Update cost[i] # to costRight cost[i] += costRight # If current element # is 1. if (arr[i] == 1): cntRight += 1 # Print cost to move all 1s for i in range(N): print(cost[i], end = " ") # Driver Code if __name__ == '__main__': arr = [ 0, 1, 0, 1 ] N = len(arr) costMove1s(arr, N) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to print the cost
// to move all 1s to each index
static void costMove1s(int []arr, int N)
{
// cost[i] Stores cost to move
// all 1s at index i
int []cost = new int[N];
// Stores count of 1s on
// the left side of index i
int cntLeft = 0;
// Stores cost to move all 1s
// from the left side of index i
// to index i
int costLeft = 0;
// Traverse the array from
// left to right.
for(int i = 0; i < N; i++)
{
// Update cost to move
// all 1s from left side
// of index i to index i
costLeft += cntLeft;
// Update cost[i] to cntLeft
cost[i] += costLeft;
// If current element is 1.
if (arr[i] == 1)
{
cntLeft++;
}
}
// Stores count of 1s on
// the right side of index i
int cntRight = 0;
// Stores cost to move all 1s
// from the right of index i
// to index i
int costRight = 0;
// Traverse the array from
// right to left.
for(int i = N - 1; i >= 0; i--)
{
// Update cost to move
// all 1s from right side
// of index i to index i
costRight += cntRight;
// Update cost[i]
// to costRight
cost[i] += costRight;
// If current element
// is 1.
if (arr[i] == 1)
{
cntRight++;
}
}
// Print cost to move all 1s
for(int i = 0; i < N; i++)
{
Console.Write(cost[i] + " ");
}
}
// Driver Code
public static void Main (String[] args)
{
int []arr = { 0, 1, 0, 1 };
int N = arr.Length;
// Function Call
costMove1s(arr, N);
}
}
// This code is contributed by math_lover
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to print the cost
// to move all 1s to each index
function costMove1s(arr, N)
{
// cost[i] Stores cost to move
// all 1s at index i
var cost = Array(N).fill(0);
// Stores count of 1s on
// the left side of index i
var cntLeft = 0;
// Stores cost to move all 1s
// from the left side of index i
// to index i
var costLeft = 0;
// Traverse the array from
// left to right.
for(var i = 0; i < N; i++)
{
// Update cost to move
// all 1s from left side
// of index i to index i
costLeft += cntLeft;
// Update cost[i] to cntLeft
cost[i] += costLeft;
// If current element is 1.
if (arr[i] == 1)
{
cntLeft++;
}
}
// Stores count of 1s on
// the right side of index i
var cntRight = 0;
// Stores cost to move all 1s
// from the right of index i
// to index i
var costRight = 0;
// Traverse the array from
// right to left.
for(var i = N - 1; i >= 0; i--)
{
// Update cost to move
// all 1s from right side
// of index i to index i
costRight += cntRight;
// Update cost[i]
// to costRight
cost[i] += costRight;
// If current element
// is 1.
if (arr[i] == 1)
{
cntRight++;
}
}
// Print cost to move all 1s
for(var i = 0; i< N; i++)
{
document.write(cost[i] + " ");
}
}
// Driver Code
var arr = [ 0, 1, 0, 1 ];
var N = arr.length;
costMove1s(arr, N);
// This code is contributed by rutvik_56
</script>
Producción:
4 2 2 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)