Divida el número N maximizando el recuento de subpartes divisibles por K

Dada una string numérica N y un entero K , la tarea es dividir los dígitos de N en subpartes de modo que se maximice el número de segmentos divisibles por K.
Nota: Podemos hacer cualquier número de cortes verticales entre pares de dígitos adyacentes. 

Ejemplos:  

Entrada: N = 32, K = 4 
Salida: 1 
Explicación: 
32 es divisible por 4 pero ninguno si sus dígitos son divisibles individualmente, por lo que no realizamos ninguna división.
Entrada: N = 2050, K = 5 
Salida: 3 
Explicación: 
2050 se puede dividir en 2, 0, 5, 0 donde 0, 5, 0 son divisibles por 5.
Entrada: N = 00001242, K = 3 
Salida: 6 
Explicación : 
00001242 se puede dividir en 0, 0, 0, 0, 12, 42 donde todas las partes son divisibles por 3.  

Enfoque: 
Para resolver el problema mencionado anteriormente, intentaremos utilizar un enfoque recursivo .  

• Verifique si hay una partición vertical entre el carácter actual y el siguiente, si no, realizamos la recursividad nuevamente para el siguiente índice y actualizamos el valor de la substring concatenando el carácter actual.
• Ahora, si hay una partición vertical entre el carácter actual y el carácter siguiente, existen dos casos:
  1. Si el presente subStr es divisible por X , entonces agregamos 1 porque el presente subStr es 1 de la respuesta posible, luego recurrimos para el siguiente índice y actualizamos subStr como una string vacía.
  2. Si el presente subStr no es divisible por X , simplemente recurrimos al siguiente índice y actualizamos subStr como una string vacía.
• Devuelve un máximo de los dos casos posibles mencionados anteriormente.

A continuación se muestra la implementación de la lógica anterior.  

// C++ program to split the number N
// by maximizing the count
// of subparts divisible by K
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the subparts
int count(string N, int X,
          string subStr,
          int index, int n)
{
 
    if (index == n)
        return 0;
 
    // Total subStr till now
    string a = subStr + N[index];
 
    // b marks the subString up till now
    // is divisible by X or not,
 
    // If it can be divided,
    // then this substring is one
    // of the possible answer
    int b = 0;
 
    // Convert string to long long and
    // check if its divisible with X
    if (stoll(a) % X == 0)
        b = 1;
 
    // Consider there is no vertical
    // cut between this index and the
    // next one, hence take total
    // carrying total substr a.
    int m1 = count(N, X, a, index + 1, n);
 
    // If there is vertical
    // cut between this index
    // and next one, then we
    // start again with subStr as ""
    // and add b for the count
    // of subStr upto now
    int m2 = b + count(N, X, "",
                       index + 1, n);
 
    // Return max of both the cases
    return max(m1, m2);
}
 
// Driver code
int main()
{
    string N = "00001242";
 
    int K = 3;
 
    int l = N.length();
 
    cout << count(N, K, "", 0, l)
         << endl;
 
    return 0;
}

// Java program to split the number N
// by maximizing the count
// of subparts divisible by K
class GFG{
 
// Function to count the subparts
static int count(String N, int X,
                 String subStr,
                 int index, int n)
{
    if (index == n)
        return 0;
 
    // Total subStr till now
    String a = subStr + N.charAt(index);
 
    // b marks the subString up till now
    // is divisible by X or not,
 
    // If it can be divided,
    // then this subString is one
    // of the possible answer
    int b = 0;
 
    // Convert String to long and
    // check if its divisible with X
    if (Long.valueOf(a) % X == 0)
        b = 1;
 
    // Consider there is no vertical
    // cut between this index and the
    // next one, hence take total
    // carrying total substr a.
    int m1 = count(N, X, a, index + 1, n);
 
    // If there is vertical
    // cut between this index
    // and next one, then we
    // start again with subStr as ""
    // and add b for the count
    // of subStr upto now
    int m2 = b + count(N, X, "",
                       index + 1, n);
 
    // Return max of both the cases
    return Math.max(m1, m2);
}
 
// Driver code
public static void main(String[] args)
{
    String N = "00001242";
 
    int K = 3;
 
    int l = N.length();
 
    System.out.print(count(N, K, "", 0, l) + "\n");
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to split the number N
# by maximizing the count
# of subparts divisible by K
 
# Function to count the subparts
def count(N, X, subStr, index, n):
     
    if (index == n):
        return 0
     
    # Total subStr till now
    a = subStr + N[index]
     
    # b marks the subString up till now
    # is divisible by X or not,
 
    # If it can be divided,
    # then this substring is one
    # of the possible answer
    b = 0
 
    # Convert string to long long and
    # check if its divisible with X
    if (int(a) % X == 0):
        b = 1
     
    # Consider there is no vertical
    # cut between this index and the
    # next one, hence take total
    # carrying total substr a.
    m1 = count(N, X, a, index + 1, n)
 
    # If there is vertical
    # cut between this index
    # and next one, then we
    # start again with subStr as ""
    # and add b for the count
    # of subStr upto now
    m2 = b + count(N, X, "", index + 1, n)
 
    # Return max of both the cases
    return max(m1, m2)
     
# Driver code
N = "00001242"
K = 3
 
l = len(N)
 
print(count(N, K, "", 0, l))
 
# This code is contributed by sanjoy_62

// C# program to split the number N
// by maximizing the count
// of subparts divisible by K
using System;
class GFG{
 
// Function to count the subparts
static int count(String N, int X,
                 String subStr,
                 int index, int n)
{
    if (index == n)
        return 0;
 
    // Total subStr till now
    String a = subStr + N[index];
 
    // b marks the subString up till now
    // is divisible by X or not,
 
    // If it can be divided,
    // then this subString is one
    // of the possible answer
    int b = 0;
 
    // Convert String to long and
    // check if its divisible with X
    if (long. Parse(a) % X == 0)
        b = 1;
 
    // Consider there is no vertical
    // cut between this index and the
    // next one, hence take total
    // carrying total substr a.
    int m1 = count(N, X, a, index + 1, n);
 
    // If there is vertical
    // cut between this index
    // and next one, then we
    // start again with subStr as ""
    // and add b for the count
    // of subStr upto now
    int m2 = b + count(N, X, "",
                  index + 1, n);
 
    // Return max of both the cases
    return Math.Max(m1, m2);
}
 
// Driver code
public static void Main(String[] args)
{
    String N = "00001242";
 
    int K = 3;
 
    int l = N.Length;
 
    Console.Write(count(N, K, "", 0, l) + "\n");
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program to split the number N
// by maximizing the count
// of subparts divisible by K
 
// Function to count the subparts
function count(N, X,
                 subStr,
                 index, n)
{
    if (index == n)
        return 0;
   
    // Total subStr till now
    let a = subStr + N[index];
   
    // b marks the subString up till now
    // is divisible by X or not,
   
    // If it can be divided,
    // then this subString is one
    // of the possible answer
    let b = 0;
   
    // Convert String to long and
    // check if its divisible with X
    if (parseInt(a) % X == 0)
        b = 1;
   
    // Consider there is no vertical
    // cut between this index and the
    // next one, hence take total
    // carrying total substr a.
    let m1 = count(N, X, a, index + 1, n);
   
    // If there is vertical
    // cut between this index
    // and next one, then we
    // start again with subStr as ""
    // and add b for the count
    // of subStr upto now
    let m2 = b + count(N, X, "",
                       index + 1, n);
   
    // Return max of both the cases
    return Math.max(m1, m2);
}
 
// Driver Code
     
    let N = "00001242";
   
    let K = 3;
   
    let l = N.length;
   
    document.write(count(N, K, "", 0, l) + "\n");
     
</script>

6