Divisiones máximas en una string binaria de modo que cada substring sea divisible por un número impar dado

Dada la string binaria str , la tarea es calcular las divisiones máximas posibles para hacer que cada substring sea divisible por un número impar K .
Ejemplos: 
 

Entrada: str = “110111001”, K = 9 
Salida: 2 
Explicación: 
Las dos substrings posibles son “11011” y “1001”. Los valores decimales equivalentes son 27 y 9 respectivamente, que son divisibles por 9.
Entrada: str = “10111001”, K = 5 
Salida: 2 
Explicación: 
Las dos substrings posibles son “101” y “11001”. Los valores decimales equivalentes son 5 y 25 respectivamente, que son divisibles por 5. 
 

Enfoque: para resolver este problema, recorremos desde el final de la cuerda y generamos la suma de la longitud recorrida. Tan pronto como la suma sea divisible por K , aumentamos el conteo en 1 y restablecemos la suma a 0, avanzamos y repetimos el mismo proceso. En el recorrido completo de la string, si la suma se ha restablecido a 0, entonces el valor de la cuenta da las máximas divisiones posibles requeridas. De lo contrario , imprima «No posible» ya que todos los segmentos no son divisibles por K.
El siguiente código es la implementación del enfoque anterior:
 

// C++ Program to split
// a given binary string
// into maximum possible
// segments divisible by
// given odd number K
 
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// maximum splits possible
void max_segments(string str, int K)
{
    int n = str.length();
    int s = 0, sum = 0, count = 0;
    for (int i = n - 1; i >= 0; i--) {
        int a = str[i] - '0';
        sum += a * pow(2, s);
 
        s++;
        if (sum != 0 && sum % K == 0) {
            count++;
            sum = 0;
            s = 0;
        }
    }
    if (sum != 0)
        cout << "-1" << endl;
    else
        cout << count << endl;
}
 
// Driver code
int main()
{
    string str = "10111001";
    int K = 5;
    max_segments(str, K);
    return 0;
}

// Java code to split a given
// binary string into maximum
// possible segments divisible
// by given odd number K
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function to calculate
// maximum splits possible
static void rearrange(String str, int K)
{
    int n = str.length();
    int s = 0, sum = 0, count = 0;
     
    for(int i = n - 1; i >= 0; i--)
    {
       int a = str.charAt(i) - '0';
       sum += a * Math.pow(2, s);
       s++;
        
       if (sum != 0 && sum % K == 0)
       {
           count++;
           sum = 0;
             s = 0;
       }
    }
  
    if (sum != 0)
        System.out.println("-1");   
    else
        System.out.println(count);
}
 
// Driver code
public static void main(String[] args)
{
    String str = "10111001";
    int K = 5;
     
    rearrange(str, K);
}
}
 
// This code is contributed by coder001

# Python3 program to split
# a given binary string
# into maximum possible
# segments divisible by
# given odd number K
 
# Function to calculate
# maximum splits possible
def max_segments(st, K):
 
    n = len(st)
    s, sum, count = 0, 0, 0
     
    for i in range(n - 1, -1, -1):
        a = ord(st[i]) - 48
        sum += a * pow(2, s)
        s += 1
         
        if (sum != 0 and sum % K == 0):
            count += 1
            sum = 0
            s = 0
             
    if (sum != 0):
        print("-1")
    else:
        print(count)
 
# Driver code
if __name__ == "__main__":
     
    st = "10111001"
    K = 5
    max_segments(st, K)
 
# This code is contributed by chitranayal

// C# program to split a given
// binary string into maximum
// possible segments divisible by
// given odd number K
using System;
 
class GFG{
     
// Function to calculate
// maximum splits possible
static void max_segments(string str, int K)
{
    int n = str.Length;
    int s = 0;
    int sum = 0;
    int count = 0;
     
    for(int i = n - 1; i >= 0; i--)
    {
       int a = str[i] - '0';
       sum += a * (int)Math.Pow(2, s);
       s++;
        
       if (sum != 0 && sum % K == 0)
       {
           count++;
           sum = 0;
             s = 0;
       }
    }
    if (sum != 0)
    {
        Console.Write("-1");
    }
    else
    {
        Console.Write(count);
    }
}
 
// Driver code
public static void Main()
{
    string str = "10111001";
    int K = 5;
     
    max_segments(str, K);
}
}
 
// This code is contributed by sayesha   

<script>
 
// Javascript code to split a given
// binary string into maximum
// possible segments divisible
// by given odd number K
  
    
// Function to calculate
// maximum splits possible
function rearrange(str , K)
{
    var n = str.length;
    var s = 0, sum = 0, count = 0;
     
    for(var i = n - 1; i >= 0; i--)
    {
       var a = str.charAt(i) - '0';
       sum += a * Math.pow(2, s);
       s++;
        
       if (sum != 0 && sum % K == 0)
       {
           count++;
           sum = 0;
             s = 0;
       }
    }
  
    if (sum != 0)
        document.write("-1");   
    else
        document.write(count);
}
 
// Driver code
var str = "10111001";
var K = 5;
 
rearrange(str, K);
 
// This code contributed by shikhasingrajput
 
</script>

2

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)