Compruebe si la representación decimal de la string binaria dada es divisible por K o no

Dada una string binaria S , la tarea es encontrar que la representación decimal de la string binaria dada es divisible por el entero K o no.

Ejemplos:

Entrada: S = 1010, k = 5
Salida: Sí
Explicación: La representación decimal de 1010 (=10) es divisible por 5

Entrada: S = 1010, k = 6
Salida: No

Enfoque:   dado que el operador de módulo es distributivo sobre la suma , la string binaria dada se puede verificar poco a poco para ver si el % k decimal es igual a cero o no. Siga los pasos a continuación para el enfoque:

• Inicialice una array poweroftwo[] , del tamaño de una string binaria , para almacenar las potencias de dos.
• Iterar hasta el tamaño y para cada i almacenar 2 ⁱ % K en poweroftwo[].
• Inicialice las variables, digamos rem = 0, para almacenar el número restante actual hasta i .
• Iterar hasta tamaño y para cada i  y si S[tamaño – i -1]  es 1 entonces actualizar rem es igual a rem + poweroftwo[i].
• Finalmente, devuelva Sí si rem es igual a cero ; de lo contrario, devuelva No.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check the binary number is
// divisible by K
string divisibleByk(string s, int n, int k)
{
    // Array poweroftwo will store pow(2, i)%k
    int poweroftwo[n];
 
    // Initializing the first element in Array
    poweroftwo[0] = 1 % k;
 
    for (int i = 1; i < n; i++) {
 
        // Storing every pow(2, i)%k value in
        // the array
        poweroftwo[i] = (poweroftwo[i - 1]
                         * (2 % k))
                        % k;
    }
 
    // To store the remaining
    int rem = 0;
 
    // Iterating till N
    for (int i = 0; i < n; i++) {
 
        // If current bit is 1
        if (s[n - i - 1] == '1') {
 
            // Updating rem
            rem += (poweroftwo[i]);
            rem %= k;
        }
    }
 
    // If completely divisible
    if (rem == 0) {
        return "Yes";
    }
 
    // If not Completely divisible
    else
        return "No";
}
 
// Driver Code
int main()
{
    // Given Input
    string s = "1010001";
    int k = 9;
 
    // length of string s
    int n = s.length();
 
    // Function Call
    cout << divisibleByk(s, n, k);
    return 0;
}

// Java program for above approach
class GFG
{
   
    // Function to check the binary number is
    // divisible by K
    public static String divisibleByk(String s, int n, int k) {
        // Array poweroftwo will store pow(2, i)%k
        int[] poweroftwo = new int[n];
 
        // Initializing the first element in Array
        poweroftwo[0] = 1 % k;
 
        for (int i = 1; i < n; i++) {
 
            // Storing every pow(2, i)%k value in
            // the array
            poweroftwo[i] = (poweroftwo[i - 1] * (2 % k)) % k;
        }
 
        // To store the remaining
        int rem = 0;
 
        // Iterating till N
        for (int i = 0; i < n; i++) {
 
            // If current bit is 1
            if (s.charAt(n - i - 1) == '1') {
 
                // Updating rem
                rem += (poweroftwo[i]);
                rem %= k;
            }
        }
 
        // If completely divisible
        if (rem == 0) {
            return "Yes";
        }
 
        // If not Completely divisible
        else
            return "No";
    }
 
    // Driver Code
    public static void main(String args[])
    {
 
      // Given Input
        String s = "1010001";
        int k = 9;
 
        // length of string s
        int n = s.length();
 
        // Function Call
        System.out.println(divisibleByk(s, n, k));
    }
 
}
 
// This code is contributed by _saurabh_jaiswal,

# python 3 program for above approach
 
# Function to check the binary number is
# divisible by K
def divisibleByk(s, n, k):
   
    # Array poweroftwo will store pow(2, i)%k
    poweroftwo = [0 for i in range(n)]
 
    # Initializing the first element in Array
    poweroftwo[0] = 1 % k
 
    for i in range(1,n,1):
        # Storing every pow(2, i)%k value in
        # the array
        poweroftwo[i] = (poweroftwo[i - 1] * (2 % k)) % k
 
    # To store the remaining
    rem = 0
 
    # Iterating till N
    for i in range(n):
       
        # If current bit is 1
        if (s[n - i - 1] == '1'):
 
            # Updating rem
            rem += (poweroftwo[i])
            rem %= k
 
    # If completely divisible
    if (rem == 0):
        return "Yes"
 
    # If not Completely divisible
    else:
        return "No"
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    s = "1010001"
    k = 9
 
    # length of string s
    n = len(s)
 
    # Function Call
    print(divisibleByk(s, n, k))
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for above approach
using System;
class GFG
{
   
    // Function to check the binary number is
    // divisible by K
    public static String divisibleByk(String s, int n, int k) {
        // Array poweroftwo will store pow(2, i)%k
        int[] poweroftwo = new int[n];
 
        // Initializing the first element in Array
        poweroftwo[0] = 1 % k;
 
        for (int i = 1; i < n; i++) {
 
            // Storing every pow(2, i)%k value in
            // the array
            poweroftwo[i] = (poweroftwo[i - 1] * (2 % k)) % k;
        }
 
        // To store the remaining
        int rem = 0;
 
        // Iterating till N
        for (int i = 0; i < n; i++) {
 
            // If current bit is 1
            if (s[n - i - 1] == '1') {
 
                // Updating rem
                rem += (poweroftwo[i]);
                rem %= k;
            }
        }
 
        // If completely divisible
        if (rem == 0) {
            return "Yes";
        }
 
        // If not Completely divisible
        else
            return "No";
    }
 
    // Driver Code
    public static void Main(String []args)
    {
 
      // Given Input
        String s = "1010001";
        int k = 9;
 
        // length of string s
        int n = s.Length;
 
        // Function Call
        Console.Write(divisibleByk(s, n, k));
    }
 
}
 
// This code is contributed by shivanisinghss2110

<script>
// Javascript program for above approach
 
// Function to check the binary number is
// divisible by K
function divisibleByk(s, n, k)
{
 
    // Array poweroftwo will store pow(2, i)%k
    let poweroftwo = new Array(n);
 
    // Initializing the first element in Array
    poweroftwo[0] = 1 % k;
 
    for (let i = 1; i < n; i++) {
 
        // Storing every pow(2, i)%k value in
        // the array
        poweroftwo[i] = (poweroftwo[i - 1]
            * (2 % k))
            % k;
    }
 
    // To store the remaining
    let rem = 0;
 
    // Iterating till N
    for (let i = 0; i < n; i++) {
 
        // If current bit is 1
        if (s[n - i - 1] == '1') {
 
            // Updating rem
            rem += (poweroftwo[i]);
            rem %= k;
        }
    }
 
    // If completely divisible
    if (rem == 0) {
        return "Yes";
    }
 
    // If not Completely divisible
    else
        return "No";
}
 
// Driver Code
 
// Given Input
let s = "1010001";
let k = 9;
 
// length of string s
let n = s.length;
 
// Function Call
document.write(divisibleByk(s, n, k));
 
// This code is contributed by gfgking.
</script>

Yes

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