Dada una array binaria y consultas Q. Cada consulta consta de un número K , la tarea es imprimir el número de unos y ceros a la izquierda del índice K .
Ejemplos:
Entrada: arr[] = {1, 1, 1, 0, 0, 1, 0, 1, 1}, Q[] = {0, 1, 2, 4}
Salida:
0 unos 0 ceros
1 unos 0 ceros
2 unos 0 ceros
3 unos 1 ceros
Entrada: arr[] = {1, 0, 1, 0, 1, 1}, Q[] = {2, 3}
Salida:
1 unos 1 ceros
2 unos 1 ceros
Enfoque: Se pueden seguir los siguientes pasos para resolver el problema anterior:
- Declare una array de pares (digamos left[] ) que se utilizará para precalcular el número de unos y ceros a la izquierda.
- Iterar en la array y en cada paso inicializar left[i] con el número de unos y ceros a la izquierda.
- El número de unos para cada consulta quedará [k].primero y el número de ceros quedará [k].segundo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to pre-calculate the left[] array
void preCalculate(int binary[], int n, pair<int, int> left[])
{
int count1 = 0, count0 = 0;
// Iterate in the binary array
for (int i = 0; i < n; i++) {
// Initialize the number
// of 1 and 0
left[i].first = count1;
left[i].second = count0;
// Increase the count
if (binary[i])
count1++;
else
count0++;
}
}
// Driver code
int main()
{
int binary[] = { 1, 1, 1, 0, 0, 1, 0, 1, 1 };
int n = sizeof(binary) / sizeof(binary[0]);
pair<int, int> left[n];
preCalculate(binary, n, left);
// Queries
int queries[] = { 0, 1, 2, 4 };
int q = sizeof(queries) / sizeof(queries[0]);
// Solve queries
for (int i = 0; i < q; i++)
cout << left[queries[i]].first << " ones "
<< left[queries[i]].second << " zeros\n";
return 0;
}
Java
// Java implementation of the approach
class GFG {
// pair class
static class pair {
int first, second;
pair(int a, int b)
{
first = a;
second = b;
}
}
// Function to pre-calculate the left[] array
static void preCalculate(int binary[], int n,
pair left[])
{
int count1 = 0, count0 = 0;
// Iterate in the binary array
for (int i = 0; i < n; i++) {
// Initialize the number
// of 1 and 0
left[i].first = count1;
left[i].second = count0;
// Increase the count
if (binary[i] != 0)
count1++;
else
count0++;
}
}
// Driver code
public static void main(String args[])
{
int binary[] = { 1, 1, 1, 0, 0, 1, 0, 1, 1 };
int n = binary.length;
pair left[] = new pair[n];
for (int i = 0; i < n; i++)
left[i] = new pair(0, 0);
preCalculate(binary, n, left);
// Queries
int queries[] = { 0, 1, 2, 4 };
int q = queries.length;
// Solve queries
for (int i = 0; i < q; i++)
System.out.println(left[queries[i]].first + " ones "
+ left[queries[i]].second + " zeros\n");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Function to pre-calculate the left[] array def preCalculate(binary, n, left): count1, count0 = 0, 0 # Iterate in the binary array for i in range(n): # Initialize the number # of 1 and 0 left[i][0] = count1 left[i][1] = count0 # Increase the count if (binary[i]): count1 += 1 else: count0 += 1 # Driver code binary = [1, 1, 1, 0, 0, 1, 0, 1, 1] n = len(binary) left = [[ 0 for i in range(2)] for i in range(n)] preCalculate(binary, n, left) queries = [0, 1, 2, 4 ] q = len(queries) # Solve queries for i in range(q): print(left[queries[i]][0], "ones", left[queries[i]][1], "zeros") # This code is contributed # by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG {
// pair class
public class pair {
public int first, second;
public pair(int a, int b)
{
first = a;
second = b;
}
}
// Function to pre-calculate the left[] array
static void preCalculate(int[] binary, int n,
pair[] left)
{
int count1 = 0, count0 = 0;
// Iterate in the binary array
for (int i = 0; i < n; i++) {
// Initialize the number
// of 1 and 0
left[i].first = count1;
left[i].second = count0;
// Increase the count
if (binary[i] != 0)
count1++;
else
count0++;
}
}
// Driver code
public static void Main(String[] args)
{
int[] binary = { 1, 1, 1, 0, 0, 1, 0, 1, 1 };
int n = binary.Length;
pair[] left = new pair[n];
for (int i = 0; i < n; i++)
left[i] = new pair(0, 0);
preCalculate(binary, n, left);
// Queries
int[] queries = { 0, 1, 2, 4 };
int q = queries.Length;
// Solve queries
for (int i = 0; i < q; i++)
Console.WriteLine(left[queries[i]].first + " ones "
+ left[queries[i]].second + " zeros\n");
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the approach
// Function to pre-calculate the left[] array
function preCalculate($binary, $n)
{
$left = array();
$count1 = 0; $count0 = 0;
// Iterate in the binary array
for ($i = 0; $i < $n; $i++)
{
// Initialize the number
// of 1 and 0
$left[$i] = array($count1,
$count0);
// Increase the count
if ($binary[$i])
$count1++;
else
$count0++;
}
return $left;
}
// Driver code
$binary = array( 1, 1, 1, 0, 0, 1, 0, 1, 1 );
$n = count($binary);
$left = preCalculate($binary, $n);
// Queries
$queries = array( 0, 1, 2, 4 );
$q = count($queries);
// Solve queries
for ($i = 0; $i < $q; $i++)
echo $left[$queries[$i]][0], " ones ",
$left[$queries[$i]][1], " zeros\n";
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to pre-calculate the left[] array
function preCalculate(binary,n,left)
{
let count1 = 0, count0 = 0;
// Iterate in the binary array
for (let i = 0; i < n; i++) {
// Initialize the number
// of 1 and 0
left[i][0] = count1;
left[i][1] = count0;
// Increase the count
if (binary[i] != 0)
count1++;
else
count0++;
}
}
// Driver code
let binary=[1, 1, 1, 0, 0, 1, 0, 1, 1];
let n = binary.length;
let left=new Array(n);
for (let i = 0; i < n; i++)
left[i] = [0, 0];
preCalculate(binary, n, left);
// Queries
let queries = [ 0, 1, 2, 4 ];
let q = queries.length;
// Solve queries
for (let i = 0; i < q; i++)
document.write(left[queries[i]][0] + " ones "
+ left[queries[i]][1] + " zeros<br>");
// This code is contributed by unknown2108
</script>
Producción:
0 ones 0 zeros 1 ones 0 zeros 2 ones 0 zeros 3 ones 1 zeros
Complejidad de tiempo: O(N+q), en cuanto al precálculo tomará O(N) tiempo porque estamos usando un bucle para recorrer N veces y O(1) para cada consulta, por lo que el tiempo total será O(q).
Espacio auxiliar: O (N), ya que estamos usando espacio adicional para la array izquierda.