Dada una array binaria que consta solo de ceros y unos. La tarea es encontrar:
- El número de subarreglos que tiene solo 1 en él.
- El número de subarreglos que tiene solo 0.
Ejemplos:
Entrada: arr[] = {0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1}
Salida:
El número de subarreglos que consisten en 0 solamente: 7
El número de subarreglos que consisten en 1 solo: 7
Entrada: arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1}
Salida:
El número de subarreglos que consisten en 0 solo: 5
El número de subarreglos compuesto por 1 solo: 15
Enfoque: Para contar 1, la idea es comenzar a recorrer la array usando un contador. Si el elemento actual es 1, incremente el contador; de lo contrario, agregue contador*(contador+1)/2 al número de subarreglos y reinicie el contador a 0. De manera similar, encuentre el número de subarreglos con solo 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the number of subarrays
// that having only 0's and only 1's
#include <bits/stdc++.h>
using namespace std;
// Function to count number of subarrays
void countSubarraysof1and0(int a[], int n)
{
int count1 = 0, count0 = 0;
int number1 = 0, number0 = 0;
// Iterate in the array to find count
// of subarrays with only 1 in it
for (int i = 0; i < n; i++) {
// check if array element
// is 1 or not
if (a[i] == 1) {
count1 += 1;
}
else {
number1 += (count1) * (count1 + 1) / 2;
count1 = 0;
}
}
// Iterate in the array to find count
// of subarrays with only 0 in it
for (int i = 0; i < n; i++) {
// check if array element
// is 0 or not
if (a[i] == 0) {
count0 += 1;
}
else {
number0 += (count0) * (count0 + 1) / 2;
count0 = 0;
}
}
// After iteration completes,
// check for the last set of subarrays
if (count1)
number1 += (count1) * (count1 + 1) / 2;
if (count0)
number0 += (count0) * (count0 + 1) / 2;
cout << "Count of subarrays of 0 only: " << number0;
cout << "\nCount of subarrays of 1 only: " << number1;
}
// Driver Code
int main()
{
int a[] = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 };
int n = sizeof(a) / sizeof(a[0]);
countSubarraysof1and0(a, n);
return 0;
}
Java
// Java program to count the number of subarrays
// that having only 0's and only 1's
import java.io.*;
class GFG {
// Function to count number of subarrays
static void countSubarraysof1and0(int a[], int n)
{
int count1 = 0, count0 = 0;
int number1 = 0, number0 = 0;
// Iterate in the array to find count
// of subarrays with only 1 in it
for (int i = 0; i < n; i++) {
// check if array element
// is 1 or not
if (a[i] == 1) {
count1 += 1;
}
else {
number1 += (count1) * (count1 + 1) / 2;
count1 = 0;
}
}
// Iterate in the array to find count
// of subarrays with only 0 in it
for (int i = 0; i < n; i++) {
// check if array element
// is 0 or not
if (a[i] == 0) {
count0 += 1;
}
else {
number0 += (count0) * (count0 + 1) / 2;
count0 = 0;
}
}
// After iteration completes,
// check for the last set of subarrays
if (count1>0)
number1 += (count1) * (count1 + 1) / 2;
if (count0>0)
number0 += (count0) * (count0 + 1) / 2;
System.out.println("Count of subarrays of 0 only: " + number0);
System.out.println( "\nCount of subarrays of 1 only: " + number1);
}
// Driver Code
public static void main (String[] args) {
int a[] = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 };
int n = a.length;
countSubarraysof1and0(a, n);;
}
}
// This code is contributed by inder_verma..
Python3
# Python 3 program to count the number of
# subarrays that having only 0's and only 1's
# Function to count number of subarrays
def countSubarraysof1and0(a, n):
count1 = 0
count0 = 0
number1 = 0
number0 = 0
# Iterate in the array to find count
# of subarrays with only 1 in it
for i in range(0, n, 1):
# check if array element is 1 or not
if (a[i] == 1):
count1 += 1
else:
number1 += ((count1) *
(count1 + 1) / 2)
count1 = 0
# Iterate in the array to find count
# of subarrays with only 0 in it
for i in range(0, n, 1):
# check if array element
# is 0 or not
if (a[i] == 0):
count0 += 1
else:
number0 += (count0) * (count0 + 1) / 2
count0 = 0
# After iteration completes,
# check for the last set of subarrays
if (count1):
number1 += (count1) * (count1 + 1) / 2
if (count0):
number0 += (count0) * (count0 + 1) / 2
print("Count of subarrays of 0 only:",
int(number0))
print("Count of subarrays of 1 only:",
int(number1))
# Driver Code
if __name__ == '__main__':
a = [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1]
n = len(a)
countSubarraysof1and0(a, n)
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to count the number of subarrays
// that having only 0's and only 1's
using System;
class GFG {
// Function to count number of subarrays
static void countSubarraysof1and0(int []a, int n)
{
int count1 = 0, count0 = 0;
int number1 = 0, number0 = 0;
// Iterate in the array to find count
// of subarrays with only 1 in it
for (int i = 0; i < n; i++) {
// check if array element
// is 1 or not
if (a[i] == 1) {
count1 += 1;
}
else {
number1 += (count1) * (count1 + 1) / 2;
count1 = 0;
}
}
// Iterate in the array to find count
// of subarrays with only 0 in it
for (int i = 0; i < n; i++) {
// check if array element
// is 0 or not
if (a[i] == 0) {
count0 += 1;
}
else {
number0 += (count0) * (count0 + 1) / 2;
count0 = 0;
}
}
// After iteration completes,
// check for the last set of subarrays
if (count1>0)
number1 += (count1) * (count1 + 1) / 2;
if (count0>0)
number0 += (count0) * (count0 + 1) / 2;
Console.WriteLine("Count of subarrays of 0 only: " + number0);
Console.WriteLine( "\nCount of subarrays of 1 only: " + number1);
}
// Driver Code
public static void Main () {
int []a = { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 };
int n = a.Length;
countSubarraysof1and0(a, n);;
}
}
// This code is contributed by inder_verma..
PHP
<?php
// PHP program to count the number
// of subarrays that having only
// 0's and only 1's
// Function to count number of subarrays
function countSubarraysof1and0($a, $n)
{
$count1 = 0; $count0 = 0;
$number1 = 0; $number0 = 0;
// Iterate in the array to find count
// of subarrays with only 1 in it
for ($i = 0; $i <$n; $i++)
{
// check if array element
// is 1 or not
if ($a[$i] == 1)
{
$count1 += 1;
}
else
{
$number1 += ($count1) *
($count1 + 1) / 2;
$count1 = 0;
}
}
// Iterate in the array to find count
// of subarrays with only 0 in it
for ($i = 0; $i <$n; $i++)
{
// check if array element
// is 0 or not
if ($a[$i] == 0)
{
$count0 += 1;
}
else
{
$number0 += ($count0) *
($count0 + 1) / 2;
$count0 = 0;
}
}
// After iteration completes,
// check for the last set of subarrays
if ($count1)
$number1 += ($count1) *
($count1 + 1) / 2;
if ($count0)
$number0 += ($count0) *
($count0 + 1) / 2;
echo "Count of subarrays of 0 only: " , $number0;
echo "\nCount of subarrays of 1 only: " , $number1;
}
// Driver Code
$a = array( 1, 1, 0, 0, 1, 0,
1, 0, 1, 1, 1, 1 );
$n = count($a);
countSubarraysof1and0($a, $n);
// This code is contributed by inder_verma
?>
Javascript
<script>
// Javascript program to count the number of subarrays
// that having only 0's and only 1's
// Function to count number of subarrays
function countSubarraysof1and0(a, n)
{
let count1 = 0, count0 = 0;
let number1 = 0, number0 = 0;
// Iterate in the array to find count
// of subarrays with only 1 in it
for (let i = 0; i < n; i++) {
// check if array element
// is 1 or not
if (a[i] == 1) {
count1 += 1;
}
else {
number1 += (count1) * (count1 + 1) / 2;
count1 = 0;
}
}
// Iterate in the array to find count
// of subarrays with only 0 in it
for (let i = 0; i < n; i++) {
// check if array element
// is 0 or not
if (a[i] == 0) {
count0 += 1;
}
else {
number0 += (count0) * (count0 + 1) / 2;
count0 = 0;
}
}
// After iteration completes,
// check for the last set of subarrays
if (count1>0)
number1 += (count1) * (count1 + 1) / 2;
if (count0>0)
number0 += (count0) * (count0 + 1) / 2;
document.write("Count of subarrays of 0 only: " + number0 + "<br/>");
document.write( "\nCount of subarrays of 1 only: " + number1);
}
// driver program
let a = [ 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 ];
let n = a.length;
countSubarraysof1and0(a, n);
</script>
Producción:
Count of subarrays of 0 only: 5 Count of subarrays of 1 only: 15
Complejidad temporal: O(N)
Espacio auxiliar: O(1)