Número de formas de formar un número con un máximo de Ks en él

Dado un número N y un dígito K , la tarea es calcular el número de formas de formar un número con el número máximo de K en él, donde en una operación, dos dígitos adyacentes de N que suman K se reemplazan con k _

Ejemplos :

Entrada : N=1454781, K=9
Salida : 2
Explicación : 9 puede ocurrir como máximo dos veces después de aplicar la operación dada y hay dos formas de hacerlo. Los dos números formados son: 19479 y 14979. 194781 no se puede formar ya que contiene 9 solo una vez, que no es el máximo.

Entrada : N=1007, K=8
Salida : 1
Explicación : No se pueden aplicar operaciones en 1007. Por lo tanto, el número máximo de 8 que pueden estar presentes es 0, y solo hay un número posible, que es 1007.

Enfoque: Las siguientes observaciones ayudan a resolver el problema:

1. Considerando el número como string, las substrings de la forma “ABAB…” donde A+B=K son los únicos segmentos del número que contribuyen a la respuesta.
2. Si la longitud de la substring contribuyente es par, solo hay una forma de aplicar las operaciones en ellos y, por lo tanto, no contribuyen a la respuesta. Por ejemplo, si la substring es «ABAB» , solo se puede cambiar a «KK» para obtener el número máximo de K en el número final .
3. De lo contrario, habrá ⌈L/2⌉ formas de obtener el número máximo de Ks , donde L es la longitud de las substrings. Por ejemplo, si la substring es «ABABA» , esto se puede convertir en lo siguiente:
   1. «KKA»
   2. «KAK»
   3. «AKK»

Siga los pasos a continuación para resolver el problema:

1. Convierta N en una string , digamos S.
2. Inicialice una respuesta variable a 1 para almacenar la respuesta final.
3. Atraviese la string S y para cada índice actual i , haga lo siguiente:
   1. Inicialice una cuenta variable a 1 , para almacenar la longitud de la respuesta actual.
   2. Repita mientras i es menor que la longitud de S , y la suma de los dígitos en S[i] y S[i-1] es igual a K , y haga lo siguiente:
      1. Incremento i .
      2. Cuenta de incrementos .
   3. Si el recuento es impar, actualice ans como ans*(count+1)/2.
4. Regresar respuesta .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate number
// of ways a number can be
// formed that has the maximum number of Ks
int noOfWays(int N, int K)
{
    // convert to string
    string S = to_string(N);
    int ans = 1;
    // calculate length of subarrays
    // that can contribute to
    // the answer
    for (int i = 1; i < S.length(); i++) {
        int count = 1;
        // count length of subarray
        // where adjacent digits
        // add up to K
        while (i < S.length()
               && S[i] - '0' + S[i - 1] - '0' == K) {
            count++;
            i++;
        }
        // Current subarray can
        // contribute to the answer
        // only if it is odd
        if (count % 2)
            ans *= (count + 1) / 2;
    }
    // return the answer
    return ans;
}
// Driver code
int main()
{
    // Input
    int N = 1454781;
    int K = 9;
 
    // Function call
    cout << noOfWays(N, K) << endl;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to calculate number
// of ways a number can be formed
// that has the maximum number of Ks
static int noOfWays(int N, int K)
{
     
    // Convert to string
    String S = String.valueOf(N);
    int ans = 1;
     
    // Calculate length of subarrays
    // that can contribute to
    // the answer
    for(int i = 1; i < S.length(); i++)
    {
        int count = 1;
         
        // Count length of subarray
        // where adjacent digits
        // add up to K
        while (i < S.length() && (int)S.charAt(i) - 48 +
              (int)S.charAt(i - 1) - 48 == K)
        {
            count++;
            i++;
        }
         
        // Current subarray can
        // contribute to the answer
        // only if it is odd
        if (count % 2 == 1)
            ans *= (count + 1) / 2;
    }
     
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Input
    int N = 1454781;
    int K = 9;
 
    // Function call
    System.out.print(noOfWays(N, K));
}   
}
 
// This code is contributed by susmitakundugoaldanga

# Python3 program for the above approach
 
# Function to calculate number of ways a
# number can be formed that has the
# maximum number of Ks
def noOfWays(N, K):
     
    # Convert to string
    S = str(N)
    ans = 1
     
    # Calculate length of subarrays
    # that can contribute to
    # the answer
    for i in range(1, len(S)):
        count = 1
         
        # Count length of subarray
        # where adjacent digits
        # add up to K
        while (i < len(S) and ord(S[i]) +
         ord(S[i - 1]) - 2 * ord('0') == K):
            count += 1
            i += 1
             
        # Current subarray can
        # contribute to the answer
        # only if it is odd
        if (count % 2):
            ans *= (count + 1) // 2
             
    # Return the answer
    return ans
     
# Driver code
if __name__ == '__main__':
     
    # Input
    N = 1454781
    K = 9
 
    # Function call
    print(noOfWays(N, K))
     
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to calculate number
// of ways a number can be
// formed that has the maximum number of Ks
static int noOfWays(int N, int K)
{
     
    // Convert to string
    string S = N.ToString();
    int ans = 1;
     
    // Calculate length of subarrays
    // that can contribute to
    // the answer
    for(int i = 1; i < S.Length; i++)
    {
        int count = 1;
         
        // Count length of subarray
        // where adjacent digits
        // add up to K
        while (i < S.Length && (int)S[i] - 48 +
              (int)S[i - 1] - 48 == K)
        {
            count++;
            i++;
        }
         
        // Current subarray can
        // contribute to the answer
        // only if it is odd
        if (count % 2 == 1)
            ans *= (count + 1) / 2;
    }
     
    // Return the answer
    return ans;
}
 
// Driver code
public static void Main()
{
     
    // Input
    int N = 1454781;
    int K = 9;
 
    // Function call
    Console.Write(noOfWays(N, K));
}
}
 
// This code is contributed by ipg2016107

<script>
 
// Javascript program for the above approach
 
// Function to calculate number
// of ways a number can be formed
// that has the maximum number of Ks
function noOfWays(N, K)
{
     
    // Convert to string
    let S = N.toString();
    let ans = 1;
     
    // Calculate length of subarrays
    // that can contribute to
    // the answer
    for(let i = 1; i < S.length; i++)
    {
        let count = 1;
         
        // Count length of subarray
        // where adjacent digits
        // add up to K
        while (i < S.length && S[i].charCodeAt() - 48 +
              S[i - 1].charCodeAt() - 48 == K)
        {
            count++;
            i++;
        }
         
        // Current subarray can
        // contribute to the answer
        // only if it is odd
        if (count % 2 == 1)
            ans *= Math.floor((count + 1) / 2);
    }
     
    // Return the answer
    return ans;
}
 
// Driver Code
 
// Input
let N = 1454781;
let K = 9;
 
// Function call
document.write(noOfWays(N, K));
 
// This code is contributed by sanjoy_62
 
</script>

2

Complejidad de Tiempo: O(Log ₁₀ N), ya que, el número de dígitos en N es Log ₁₀ N
Espacio Auxiliar: O(1)