Divisibilidad por 64 con eliminación de bits permitida

Dada una string binaria, debemos verificar si ese número es divisible por 64 o no después de eliminar algunos bits. En caso afirmativo, escriba «posible», de lo contrario, «no es posible». No podemos hacer el número 0 para hacerlo divisible.
Ejemplo : 
 

Input: 100010001 
Output: Possible
Explanation: We can get string 1 000 000 
after removing two ones which is a 
representation of number 64 in the binary 
numerical system.

Input: 100
Output: Not possible
Explanation : The number is 4 which is not 
divisible by 64 or cannot be made possible 
my removing some digits.

Si tenemos 6 ceros después de uno, entonces podemos eliminar otros bits y representarlo como un múltiplo de 64. Entonces, solo necesitamos verificar si hay un 1 antes de seis ceros. 
 

// CPP program to find if given binary string can
// become divisible by 64 after removing some bits.
#include <iostream>
using namespace std;
 
// function to check if it is possible
// to make it a multiple of 64.
bool checking(string s)
{
    int c = 0; // counter to count 0's
    int n = s.length(); // length of the string
 
    // loop which traverses right to left and
    // calculates the number of zeros before 1.
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '0')
            c++;
 
        if (c >= 6 and s[i] == '1')
            return true;
    }
 
    return false;
}
 
// driver code
int main()
{
    string s = "100010001";
    if (checking(s))
        cout << "Possible";
    else
        cout << "Not possible";
    return 0;
}

// Java program to find if
// given binary string can
// become divisible by
// 64 after removing some bits
import java.io.*;
 
class GFG
{
    // function to check if it is possible
    // to make it a multiple of 64.
    static boolean checking(String s)
    {
        // counter to count 0's
        int c = 0;
         
        // length of the string
        int n = s.length();
     
        // loop which traverses right to left and
        // calculates the number of zeros before 1.
        for (int i = n - 1; i >= 0; i--)
        {
            if (s.charAt(i) == '0')
                c++;
     
            if (c >= 6 && s.charAt(i) == '1')
                return true;
        }
     
        return false;
    }
 
    // Driver code
    public static void main (String[] args)
    {
        String s = "100010001";
        if (checking(s))
            System.out.println ( "Possible");
        else
            System.out.println ( "Not possible");
     
    }
}
 
// This code  is contributed by vt_m

# Python 3 program to find if given binary
# string can become divisible by 64 after
# removing some bits.
 
# function to check if it is possible
# to make it a multiple of 64.
def checking(s):
    c = 0
     
    # counter to count 0's
    n = len(s)
     
    # length of the string
 
    # loop which traverses right to left and
    # calculates the number of zeros before 1.
    i = n - 1
    while(i >= 0):
        if (s[i] == '0'):
            c += 1
 
        if (c >= 6 and s[i] == '1'):
            return True
         
        i -= 1
     
    return False
 
# Driver code
if __name__ == '__main__':
    s = "100010001"
    if (checking(s)):
        print("Possible")
    else:
        print("Not possible")
     
# This code is contributed by
# Surendra_Gangwar

// C# program to find if given binary
// string can become divisible by 64
// after removing some bits
using System;
 
class GFG {
     
    // function to check if it is possible
    // to make it a multiple of 64.
    static bool checking(string s)
    {
         
        // counter to count 0's
        int c = 0;
         
        // length of the string
        int n = s.Length;
     
        // loop which traverses right to
        // left and calculates the number
        // of zeros before 1.
        for (int i = n - 1; i >= 0; i--)
        {
            if (s[i] == '0')
                c++;
     
            if (c >= 6 && s[i] == '1')
                return true;
        }
     
        return false;
    }
 
    // Driver code
    public static void Main ()
    {
        String s = "100010001";
         
        if (checking(s))
            Console.WriteLine (
                          "Possible");
        else
            Console.WriteLine(
                     "Not possible");
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find if
// given binary string can
// become divisible by 64
// after removing some bits.
 
// function to check if
// it is possible
// to make it a multiple of 64.
 
function checking($s)
{
    // counter to count 0's
    $c = 0;
     
    // length of the string
    $n = strlen($s);
 
    // loop which traverses right
    // to left and calculates the
    // number of zeros before 1.
    for ($i = $n - 1; $i >= 0; $i--)
    {
        if ($s[$i] == '0')
            $c++;
 
        if ($c >= 6 and $s[$i] == '1')
            return true;
    }
 
    return false;
}
 
// Driver Code
$s = "100010001";
if (checking($s))
    echo "Possible";
else
    echo "Not possible";
 
// This code is contributed by ajit
?>

<script>
 
// Javascript program to find if given binary
// string can become divisible by 64
// after removing some bits
 
    // function to check if it is possible
    // to make it a multiple of 64.
    function checking(s)
    {
           
        // counter to count 0's
        let c = 0;
           
        // length of the string
        let n = s.length;
       
        // loop which traverses right to
        // left and calculates the number
        // of zeros before 1.
        for (let i = n - 1; i >= 0; i--)
        {
            if (s[i] == '0')
                c++;
       
            if (c >= 6 && s[i] == '1')
                return true;
        }
       
        return false;
    }
     
// Driver code
        let s = "100010001";
           
        if (checking(s))
            document.write(
                          "Possible");
        else
            document.write(
                     "Not possible");
    
   // This code is contributed by code_hunt.
</script>

Producción : 
 

Possible

Complejidad de tiempo: O (longitud de string)

Complejidad espacial: O(1)
 

Este artículo es una contribución de Twinkle Bajaj . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.