Se da una array binaria no vacía A que consta de tamaño N donde,
0 represents a car traveling east, 1 represents a car traveling west.
El objetivo es contar los coches que pasan. Decimos que un par de autos (P, Q), donde 0 <= P < Q < N, está pasando cuando P viaja hacia el este y Q hacia el oeste.
Ejemplos:
Input : arr[] = {0, 1, 0, 1, 1}
Output : 5
The 5 pairs are (A[0], A[1]), (A[0], A[3]), (A[0], A[4]),
(A[2], A[3]) and (A[2], A[4]). Note that in all pairs
first element is 0, second element is 1 and index of
first element is smaller than index of second element.
Input : arr[] = {1, 0, 0, 0, 1}
Output : 3
Input : arr[] = {0, 0, 1, 0, 0}
Output : 2
Una solución simple es usar dos bucles anidados. El ciclo externo busca un 0, el ciclo interno cuenta un número de 1 después de 0. Finalmente, devolvemos el recuento total.
Implementación:
C++
// Simple C++ program to count passing cars
#include<bits/stdc++.h>
using namespace std;
// Returns count of passing cars
int getPassingCars(int A[], int n)
{
int result = 0;
for (int i=0; i<n-1; i++)
{
if (A[i] == 0)
{
for (int j=i+1; j<n; j++)
if (A[j])
result++;
}
}
return result;
}
// Driver program
int main()
{
int A[] = {0, 1, 0, 1, 1};
int n = sizeof(A)/sizeof(A[0]);
cout << getPassingCars(A, n);
return 0;
}
Java
// Simple Java program to count passing cars
class GFG
{
// Returns count of passing cars
static int getPassingCars(int[] A, int n)
{
int result = 0;
for (int i = 0; i < n - 1; i++)
{
if (A[i] == 0)
{
for (int j = i + 1; j < n; j++)
if (A[j] == 1)
result++;
}
}
return result;
}
// Driver Code
public static void main(String[] args)
{
int[] A = {0, 1, 0, 1, 1};
int n = A.length;
System.out.println(getPassingCars(A, n));
}
}
// This code is contributed
// by Code_Mech
Python3
# Simple Python 3 program to # count passing cars # Returns count of passing cars def getPassingCars(A, n): result = 0 for i in range(0, n - 1, 1): if (A[i] == 0): for j in range(i + 1, n, 1): if (A[j]): result += 1 return result # Driver Code if __name__ == '__main__': A = [0, 1, 0, 1, 1] n = len(A) print(getPassingCars(A, n)) # This code is contributed by # Sanjit_Prasad
C#
// Simple C# program to count passing cars
using System;
class GFG
{
// Returns count of passing cars
static int getPassingCars(int[] A, int n)
{
int result = 0;
for (int i = 0; i < n - 1; i++)
{
if (A[i] == 0)
{
for (int j = i + 1; j < n; j++)
if (A[j] == 1)
result++;
}
}
return result;
}
// Driver Code
public static void Main()
{
int[] A = {0, 1, 0, 1, 1};
int n = A.Length;
Console.WriteLine(getPassingCars(A, n));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// Simple PHP program to count passing cars
// Returns count of passing cars
function getPassingCars($A, $n)
{
$result = 0;
for ($i = 0; $i < $n - 1; $i++)
{
if ($A[$i] == 0)
{
for ($j = $i + 1; $j < $n; $j++)
if ($A[$j])
$result++;
}
}
return $result;
}
// Driver Code
$A = array(0, 1, 0, 1, 1);
$n = sizeof($A);
echo getPassingCars($A, $n);
// This code is contributed by m_kit
?>
Javascript
<script>
// Simple Javascript program
// to count passing cars
// Returns count of passing cars
function getPassingCars(A, n)
{
let result = 0;
for (let i = 0; i < n - 1; i++)
{
if (A[i] == 0)
{
for (let j = i + 1; j < n; j++)
if (A[j] == 1)
result++;
}
}
return result;
}
let A = [0, 1, 0, 1, 1];
let n = A.length;
document.write(getPassingCars(A, n));
</script>
Producción
5
Complejidad de Tiempo : O(n 2 )
Espacio Auxiliar : O(1)
Una solución eficiente para atravesar una array desde la derecha, realizar un seguimiento de los recuentos de 1 desde la derecha. Cada vez que vemos un 0, incrementamos el resultado en 1s.
Implementación:
C++
// Efficient C++ program to count passing cars
#include<bits/stdc++.h>
using namespace std;
// Returns count of passing cars
int getPassingCars(int A[], int n)
{
// Initialize count of 1s from right
// and result
int countOne = 0, result = 0;
while (n >= 1)
{
if (A[n-1] == 1)
countOne++;
else
result += countOne;
n--;
}
return result;
}
// Driver program
int main()
{
int A[] = {0, 1, 0, 1, 1};
int n = sizeof(A)/sizeof(A[0]);
cout << getPassingCars(A, n);
return 0;
}
Java
// Efficient Java program to count passing cars
class GFG
{
// Returns count of passing cars
static int getPassingCars(int A[], int n)
{
// Initialize count of 1s from right
// and result
int countOne = 0, result = 0;
while (n >= 1)
{
if (A[n-1] == 1)
countOne++;
else
result += countOne;
n--;
}
return result;
}
// Driver code
public static void main(String[] args)
{
int A[] = {0, 1, 0, 1, 1};
int n = A.length;
System.out.println(getPassingCars(A, n));
}
}
// This code is contributed by Mukul Singh.
Python3
# Efficient Python3 program to # count passing cars # Returns count of passing cars def getPassingCars(A, n): # Initialize count of 1s # from right and result countOne = 0; result = 0 while n >= 1: if A[n - 1] == 1: countOne += 1 else: result += countOne n -= 1 return result # Driver code A = [0, 1, 0, 1, 1] n = len(A) print(getPassingCars(A, n)) # This code is contributed # by Shrikant13
C#
// Efficient C# program to
// count passing cars
using System;
class GFG
{
// Returns count of passing cars
static int getPassingCars(int []A, int n)
{
// Initialize count of 1s from right
// and result
int countOne = 0, result = 0;
while (n >= 1)
{
if (A[n - 1] == 1)
countOne++;
else
result += countOne;
n--;
}
return result;
}
// Driver code
public static void Main()
{
int []A = {0, 1, 0, 1, 1};
int n = A.Length;
Console.Write(getPassingCars(A, n));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// Efficient PHP program to count passing cars
// Returns count of passing cars
function getPassingCars($A, $n)
{
// Initialize count of 1s from right
// and result
$countOne = 0; $result = 0;
while ($n >= 1)
{
if ($A[$n-1] == 1)
$countOne++;
else
$result += $countOne;
$n--;
}
return $result;
}
// Driver Code
$A = array(0, 1, 0, 1, 1);
$n = sizeof($A);
echo getPassingCars($A, $n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Efficient Javascript program to count passing cars
// Returns count of passing cars
function getPassingCars(A, n)
{
// Initialize count of 1s from right
// and result
let countOne = 0, result = 0;
while (n >= 1)
{
if (A[n - 1] == 1)
countOne++;
else
result += countOne;
n--;
}
return result;
}
let A = [0, 1, 0, 1, 1];
let n = A.length;
document.write(getPassingCars(A, n));
</script>
Producción
5
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Rakesh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA