Ocurrencias de un patrón en la representación binaria de un número

Posted on by Rudeus Greyrat

Dada una string pat y un número entero N , la tarea es encontrar el número de ocurrencias del patrón pat en la representación binaria de N.
Ejemplos: 
 

Entrada: N = 2, pat = “101” 
Salida: 0 
El patrón “101” no ocurre en la representación binaria de 2 (10).
Entrada: N = 10, pat = “101” 
Salida: 1  La
representación binaria de 10 es 1010 y el patrón dado ocurre solo una vez. 
 

Enfoque ingenuo: convierta el número en su representación de string binaria y luego use un algoritmo de coincidencia de patrones para verificar la cantidad de veces que el patrón ha ocurrido en la representación binaria.
Enfoque eficiente: 
 

  1. Convierta el patrón binario en su representación decimal.
  2. Tome un entero all_ones , cuya representación binaria consta de todos los bits establecidos (igual al número de bits en el patrón).
  3. Ejecutar N & all_ones ahora dejará solo los últimos k bits sin cambios (otros serán 0) donde k es el número de bits en el patrón.
  4. Ahora bien, si N = patrón , significa que N contenía el patrón al final en su representación binaria. Entonces actualice count = count + 1 .
  5. Desplace N a la derecha de 1 y repita los dos pasos anteriores hasta que N ≥ patrón & N > 0 .
  6. Imprime el conteo al final.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find the number of times
// pattern p occurred in binary representation
// on n.
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of occurrence
// of pat in binary representation of n
int countPattern(int n, string pat)
{
    // To store decimal value of the pattern
    int pattern_int = 0;
 
    int power_two = 1;
 
    // To store a number that has all ones in
    // its binary representation and length
    // of ones equal to length of the pattern
    int all_ones = 0;
 
    // Find values of pattern_int and all_ones
    for (int i = pat.length() - 1; i >= 0; i--) {
        int current_bit = pat[i] - '0';
        pattern_int += (power_two * current_bit);
        all_ones = all_ones + power_two;
        power_two = power_two * 2;
    }
 
    int count = 0;
    while (n && n >= pattern_int) {
 
        // If the pattern occurs in the last
        // digits of n
        if ((n & all_ones) == pattern_int) {
            count++;
        }
 
        // Right shift n by 1 bit
        n = n >> 1;
    }
    return count;
}
 
// Driver code
int main()
{
    int n = 500;
    string pat = "10";
    cout << countPattern(n, pat);
}

Java

// Java program to find the number of times
// pattern p occurred in binary representation
// on n.
import java.util.*;
 
class solution
{
 
// Function to return the count of occurrence
// of pat in binary representation of n
static int countPattern(int n, String pat)
{
    // To store decimal value of the pattern
    int pattern_int = 0;
 
    int power_two = 1;
 
    // To store a number that has all ones in
    // its binary representation and length
    // of ones equal to length of the pattern
    int all_ones = 0;
 
    // Find values of pattern_int and all_ones
    for (int i = pat.length() - 1; i >= 0; i--) {
        int current_bit = pat.charAt(i) - '0';
        pattern_int += (power_two * current_bit);
        all_ones = all_ones + power_two;
        power_two = power_two * 2;
    }
 
    int count = 0;
    while (n!=0 && n >= pattern_int) {
 
        // If the pattern occurs in the last
        // digits of n
        if ((n & all_ones) == pattern_int) {
            count++;
        }
 
        // Right shift n by 1 bit
        n = n >> 1;
    }
    return count;
}
 
// Driver code
public static void main(String args[])
{
    int n = 500;
    String pat = "10";
    System.out.println(countPattern(n, pat));
}
}

Python3

# Python 3 program to find the number of times
# pattern p occurred in binary representation
# on n.
 
# Function to return the count of occurrence
# of pat in binary representation of n
def countPattern(n, pat):
     
    # To store decimal value of the pattern
    pattern_int = 0
 
    power_two = 1
 
    # To store a number that has all ones in
    # its binary representation and length
    # of ones equal to length of the pattern
    all_ones = 0
 
    # Find values of pattern_int and all_ones
    i = len(pat) - 1
    while(i >= 0):
        current_bit = ord(pat[i]) - ord('0')
        pattern_int += (power_two * current_bit)
        all_ones = all_ones + power_two
        power_two = power_two * 2
        i -= 1
     
    count = 0
    while (n != 0 and n >= pattern_int):
         
        # If the pattern occurs in the last
        # digits of n
        if ((n & all_ones) == pattern_int):
            count += 1
         
        # Right shift n by 1 bit
        n = n >> 1
     
    return count
 
# Driver code
if __name__ == '__main__':
    n = 500
    pat = "10"
    print(countPattern(n, pat))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find the number of times
// pattern p occurred in binary representation
// on n.
using System ;
 
class GFG
{
 
// Function to return the count of occurrence
// of pat in binary representation of n
static int countPattern(int n, string pat)
{
    // To store decimal value of the pattern
    int pattern_int = 0;
 
    int power_two = 1;
 
    // To store a number that has all ones in
    // its binary representation and length
    // of ones equal to length of the pattern
    int all_ones = 0;
 
    // Find values of pattern_int and all_ones
    for (int i = pat.Length - 1; i >= 0; i--)
    {
        int current_bit = pat[i] - '0';
        pattern_int += (power_two * current_bit);
        all_ones = all_ones + power_two;
        power_two = power_two * 2;
    }
 
    int count = 0;
    while (n != 0 && n >= pattern_int)
    {
 
        // If the pattern occurs in the last
        // digits of n
        if ((n & all_ones) == pattern_int)
        {
            count++;
        }
 
        // Right shift n by 1 bit
        n = n >> 1;
    }
    return count;
}
 
// Driver code
public static void Main()
{
    int n = 500;
    string pat = "10";
    Console.WriteLine(countPattern(n, pat));
}
}
 
// This code is contributed by Ryuga

PHP

<?php
// PHP program to find the number of times
// pattern pat occurred in binary representation
// of n.
 
// Function to return the count of occurrence
// of pat in binary representation of n
function countPattern($n, $pat)
{
    // To store decimal value of the pattern
    $pattern_int = 0;
 
    $power_two = 1;
 
    // To store a number that has all ones in
    // its binary representation and length
    // of ones equal to length of the pattern
    $all_ones = 0;
 
    // Find values of $pattern_int and $all_ones
    for ($i = strlen($pat) - 1; $i >= 0; $i--)
    {
        $current_bit = $pat[$i] - '0';
        $pattern_int += ($power_two * $current_bit);
        $all_ones = $all_ones + $power_two;
        $power_two = $power_two * 2;
    }
 
    $count = 0;
    while ($n && $n >= $pattern_int)
    {
 
        // If the pattern occurs in the last
        // digits of $n
        if (($n & $all_ones) == $pattern_int)
        {
            $count++;
        }
 
        // Right shift $n by 1 bit
        $n = $n >> 1;
    }
    return $count;
}
 
// Driver code
$n = 500;
$pat = "10";
echo countPattern($n, $pat);
 
// This code is contributed by ihritik
?>

Javascript

<script>
 
// Javascript program to find the number of times
// pattern p occurred in binary representation
// on n.
 
 
// Function to return the count of occurrence
// of pat in binary representation of n
function countPattern( n, pat)
{
    // To store decimal value of the pattern
    let pattern_int = 0;
 
    let power_two = 1;
 
    // To store a number that has all ones in
    // its binary representation and length
    // of ones equal to length of the pattern
    let all_ones = 0;
 
    // Find values of pattern_int and all_ones
    for (let i = pat.length - 1; i >= 0; i--) {
        let current_bit = pat.charAt(i) - '0';
        pattern_int += (power_two * current_bit);
        all_ones = all_ones + power_two;
        power_two = power_two * 2;
    }
 
    let count = 0;
    while (n!=0 && n >= pattern_int) {
 
        // If the pattern occurs in the last
        // digits of n
        if ((n & all_ones) == pattern_int) {
            count++;
        }
 
        // Right shift n by 1 bit
        n = n >> 1;
    }
    return count;
}
 
// Driver Code
 
let n = 500;
let pat = "10";
document.write(countPattern(n, pat));
 
</script>
Producción: 

2

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por aatif y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *