Dada una array binaria arr[] y un entero x , la tarea es contar todos los prefijos de la array dada que son divisibles por x .
Nota: El i -ésimo prefijo de arr[0] a arr[i] se interpreta como un número binario (del bit más significativo al bit menos significativo).
Ejemplos:
Entrada: arr[] = {0, 1, 0, 1, 1}, x = 5
Salida: 2
0 = 0
01 = 1
010 = 2
0101 = 5
01011 = 11
0 y 0101 son los únicos prefijos divisibles por 5.
Entrada: arr[] = {1, 0, 1, 0, 1, 1, 0}, x = 2
Salida: 3
Enfoque ingenuo: iterar de 0 a i para convertir cada prefijo binario a decimal y verificar si el número es divisible por x o no.
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 return the count of total
// binary prefix which are divisible by x
int CntDivbyX(int arr[], int n, int x)
{
// Initialize with zero
int number = 0;
int count = 0;
for (int i = 0; i < n; i++) {
// Convert all prefixes to decimal
number = number * 2 + arr[i];
// If number is divisible by x
// then increase count
if ((number % x == 0))
count += 1;
}
return count;
}
// Driver code
int main()
{
int arr[] = { 1, 0, 1, 0, 1, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
cout << CntDivbyX(arr, n, x);
return 0;
}
Java
// Java implementation of the approach
class GfG
{
// Function to return the count of total
// binary prefix which are divisible by x
static int CntDivbyX(int arr[], int n, int x)
{
// Initialize with zero
int number = 0;
int count = 0;
for (int i = 0; i < n; i++)
{
// Convert all prefixes to decimal
number = number * 2 + arr[i];
// If number is divisible by x
// then increase count
if ((number % x == 0))
count += 1;
}
return count;
}
// Driver Code
public static void main(String []args)
{
int arr[] = { 1, 0, 1, 0, 1, 1, 0 };
int n = arr.length;
int x = 2;
System.out.println(CntDivbyX(arr, n, x));
}
}
// This code is contributed by Rituraj Jain
Python3
# Python 3 implementation of the approach # Function to return the count of total # binary prefix which are divisible by x def CntDivbyX(arr, n, x): # Initialize with zero number = 0 count = 0 for i in range(n): # Convert all prefixes to decimal number = number * 2 + arr[i] # If number is divisible by x # then increase count if ((number % x == 0)): count += 1 return count # Driver code if __name__ == '__main__': arr = [1, 0, 1, 0, 1, 1, 0] n = len(arr) x = 2 print(CntDivbyX(arr, n, x)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GfG
{
// Function to return the count of total
// binary prefix which are divisible by x
static int CntDivbyX(int[] arr, int n, int x)
{
// Initialize with zero
int number = 0;
int count = 0;
for (int i = 0; i < n; i++)
{
// Convert all prefixes to decimal
number = number * 2 + arr[i];
// If number is divisible by x
// then increase count
if ((number % x == 0))
count += 1;
}
return count;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 0, 1, 0, 1, 1, 0 };
int n = arr.Length;
int x = 2;
Console.WriteLine(CntDivbyX(arr, n, x));
}
}
// This code is contributed by Code_Mech.
PHP
<?php
// PHP implementation of the approach
// Function to return the count of total
// binary prefix which are divisible by x
function CntDivbyX($arr, $n, $x)
{
// Initialize with zero
$number = 0;
$count = 0;
for ($i = 0; $i < $n; $i++)
{
// Convert all prefixes to decimal
$number = $number * 2 + $arr[$i];
// If number is divisible by x
// then increase count
if (($number % $x == 0))
$count += 1;
}
return $count;
}
// Driver code
$arr = array(1, 0, 1, 0, 1, 1, 0);
$n = sizeof($arr);
$x = 2;
echo CntDivbyX($arr, $n, $x);
// This code is contributed by Akanksha Rai
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of total
// binary prefix which are divisible by x
function CntDivbyX(arr, n, x)
{
// Initialize with zero
let number = 0;
let count = 0;
for (let i = 0; i < n; i++) {
// Convert all prefixes to decimal
number = number * 2 + arr[i];
// If number is divisible by x
// then increase count
if ((number % x == 0))
count += 1;
}
return count;
}
// Driver code
let arr = [ 1, 0, 1, 0, 1, 1, 0 ];
let n = arr.length;
let x = 2;
document.write(CntDivbyX(arr, n, x));
</script>
3
Complejidad de tiempo: O(N) donde N es el tamaño de la array
Espacio auxiliar: O(1)
Enfoque eficiente: como vemos en el enfoque anterior, convertimos cada prefijo binario en un número decimal como 0, 01, 010, 0101…. pero a medida que aumenta el valor de n (tamaño de la array), el número resultante será muy grande y no. estará fuera del rango del tipo de datos, por lo que podemos hacer uso de las propiedades modulares.
En lugar de hacer número = número * 2 + arr[ i ] , podemos hacerlo mejor como número = (número * 2 + arr[ i ] ) % x
Explicación: empezamos con número = 0 y repetidamente hacemos número = número * 2 + arr[ i ] luego, en cada iteración, obtendremos un nuevo término de la secuencia anterior.
A = {1, 0, 1, 0, 1, 1, 0}
“1” = 0*2 + 1 = 1
“10” = 1*2 + 0 = 2
“101” = 2*2 + 1 = 5
“1010” = 5*2 + 0 = 10
“10101” = 10*2 + 1 = 21
“101011” = 21*2 + 1 = 43
“1010110” = 43*2 + 0 =86
Dado que estamos tomando repetidamente los restos del número en cada paso, en cada paso tenemos, newNum = oldNum * 2 + arr[i] . Según las reglas de la aritmética modular (a * b + c) % m es lo mismo que ( (a * b) % m + c % m) % m . Entonces, no importa si oldNum es el resto o el número original, la respuesta sería correcta.
Nota: Artículo similar discutido aquí .
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 return the count of total
// binary prefix which are divisible by x
int CntDivbyX(int arr[], int n, int x)
{
// Initialize with zero
int number = 0;
int count = 0;
for (int i = 0; i < n; i++) {
// Instead of converting all prefixes
// to decimal, take reminder with x
number = (number * 2 + arr[i]) % x;
// If number is divisible by x
// then reminder = 0
if (number == 0)
count += 1;
}
return count;
}
// Driver code
int main()
{
int arr[] = { 1, 0, 1, 0, 1, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
cout << CntDivbyX(arr, n, x);
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function to return the count of total
// binary prefix which are divisible by x
public static int CntDivbyX(int arr[], int n, int x)
{
// Initialize with zero
int number = 0;
int count = 0;
for (int i = 0; i < n; i++) {
// Instead of converting all prefixes
// to decimal, take reminder with x
number = (number * 2 + arr[i]) % x;
// If number is divisible by x
// then reminder = 0
if (number == 0)
count += 1;
}
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 0, 1, 0, 1, 1, 0 };
int n = 7;
int x = 2;
System.out.print(CntDivbyX(arr, n, x));
}
}
Python3
# Python3 implementation of the approach # Function to return the count of total # binary prefix which are divisible by x def CntDivbyX(arr, n, x): number = 0 count = 0 for i in range (0, n): # Instead of converting all prefixes # to decimal, take reminder with x number = ( number * 2 + arr[i] ) % x # If number is divisible by x # then reminder = 0 if number == 0: count += 1 return count # Driver code arr = [1, 0, 1, 0, 1, 1, 0] n = 7 x = 2 print( CntDivbyX(arr, n, x) )
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of total
// binary prefix which are divisible by x
public static int CntDivbyX(int []arr, int n, int x)
{
// Initialize with zero
int number = 0;
int count = 0;
for (int i = 0; i < n; i++)
{
// Instead of converting all prefixes
// to decimal, take reminder with x
number = (number * 2 + arr[i]) % x;
// If number is divisible by x
// then reminder = 0
if (number == 0)
count += 1;
}
return count;
}
// Driver code
public static void Main()
{
int []arr = { 1, 0, 1, 0, 1, 1, 0 };
int n = 7;
int x = 2;
Console.Write(CntDivbyX(arr, n, x));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to return the count of total
// binary prefix which are divisible by x
function CntDivbyX($arr, $n, $x)
{
// Initialize with zero
$number = 0;
$count1 = 0;
for ($i = 0; $i < $n; $i++)
{
// Instead of converting all prefixes
// to decimal, take reminder with x
$number = ($number * 2 + $arr[$i]) % $x;
// If number is divisible by x
// then reminder = 0
if ($number == 0)
$count1 += 1;
}
return $count1;
}
// Driver code
$arr = array(1, 0, 1, 0, 1, 1, 0);
$n = sizeof($arr);
$x = 2;
echo CntDivbyX($arr, $n, $x);
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of total
// binary prefix which are divisible by x
function CntDivbyX(arr, n, x)
{
// Initialize with zero
let number = 0;
let count = 0;
for (let i = 0; i < n; i++) {
// Instead of converting all prefixes
// to decimal, take reminder with x
number = (number * 2 + arr[i]) % x;
// If number is divisible by x
// then reminder = 0
if (number == 0)
count += 1;
}
return count;
}
// Driver code
let arr = [ 1, 0, 1, 0, 1, 1, 0 ];
let n = arr.length;
let x = 2;
document.write(CntDivbyX(arr, n, x));
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA