Contar formas de hacer que el número formado por K concatenaciones de una string numérica sea divisible por 5

Posted on by Rudeus Greyrat

Dada una string S que consta de N dígitos y un número entero K , la tarea es contar el número de formas de eliminar dígitos del número formado por la concatenación de la string S , K número de veces, de modo que la string resultante sea divisible por 5 . Dado que el conteo puede ser muy grande, imprímalo en módulo 10 9 + 7 .

Ejemplos:

Entrada: S = 1256, K = 1
Salida: 4
Explicación: Las
siguientes son las formas de eliminar los caracteres para que la string S(= “1256”) sea divisible por 5:

  1. Eliminar el carácter 6 de la string S modifica la string a 125, que es divisible por 5.
  2. Elimine el carácter 1 y 6 de la string S modifica la string a 25, que es divisible por 5.
  3. Elimine el carácter 2 y 6 de la string S modifica la string a 15, que es divisible por 5.
  4. Elimina los caracteres 1, 2 y 6 de la string S modifica la string a 5, que es divisible por 5.

Por lo tanto, la cuenta total de números formados que es divisible por 5 es 4.

Entrada: S = 13390, K = 2
Salida: 528

Enfoque: El problema dado se puede resolver por el hecho de que el número es divisible por 5 si y solo si su último dígito es 0 o 5 . Si sol[i] es el número de formas de formar los números divisibles por 5 que terminan en i , entonces la cuenta de números viene dada por (sol[1] + sol[2] + … + sol[N]) . Para cada índice i , a la derecha de i , la opción es eliminar todos los dígitos ya la izquierda de i , luego hay dos opciones, eliminar o tomar, es decir, 2 (i – 1) . 

Por lo tanto, la cuenta total de números para K número de concatenación viene dada por:

respuesta = respuesta * (2 (K*N) -1) / (2 N – 1)

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
 
// Function to find the value of a^b
// modulo 1000000007
int exp_mod(LL a, LL b)
{
 
    // Stores the resultant value a^b
    LL ret = 1;
 
    // Find the value of a^b
    for (; b; b >>= 1, a = a * a % MOD) {
        if (b & 1)
            ret = ret * a % MOD;
    }
 
    return ret;
}
 
// Function to count the number of ways
// such that the formed number is divisible
// by 5 by removing digits
int countOfWays(string s, int k)
{
    int N = s.size();
 
    // Stores the count of ways
    LL ans = 0;
 
    // Find the count for string S
    for (int i = 0; i < N; i++) {
 
        // If the digit is 5 or 0
        if (s[i] == '5' || s[i] == '0') {
            ans = (ans + exp_mod(2, i)) % MOD;
        }
    }
 
    // Find the count of string for K
    // concatenation of string S
    LL q = exp_mod(2, N);
    LL qk = exp_mod(q, k);
    LL inv = exp_mod(q - 1, MOD - 2);
 
    // Find the total count
    ans = ans * (qk - 1) % MOD;
    ans = ans * inv % MOD;
 
    return ans;
}
 
// Driver Code
int main()
{
    string S = "1256";
    int K = 1;
    cout << countOfWays(S, K);
 
    return 0;
}

Java

// Java program for the above approach
class GFG
{
  static long MOD = 1000000007;
 
  // Function to find the value of a^b
  // modulo 1000000007
  public static long exp_mod(long a, long b) {
 
    // Stores the resultant value a^b
    long ret = 1;
 
    // Find the value of a^b
    for (; b > 0; b >>= 1, a = a * a % MOD) {
      if ((b & 1) > 0)
        ret = ret * a % MOD;
    }
 
    return ret;
  }
 
  // Function to count the number of ways
  // such that the formed number is divisible
  // by 5 by removing digits
  public static long countOfWays(String s, int k) {
    int N = s.length();
 
    // Stores the count of ways
    long ans = 0;
 
    // Find the count for string S
    for (int i = 0; i < N; i++) {
 
      // If the digit is 5 or 0
      if (s.charAt(i) == '5' || s.charAt(0) == '0') {
        ans = (ans + exp_mod(2, i)) % MOD;
      }
    }
 
    // Find the count of string for K
    // concatenation of string S
    long q = exp_mod(2, N);
    long qk = exp_mod(q, k);
    long inv = exp_mod(q - 1, MOD - 2);
 
    // Find the total count
    ans = ans * (qk - 1) % MOD;
    ans = ans * inv % MOD;
 
    return ans;
  }
 
  // Driver Code
  public static void main(String args[]) {
    String S = "1256";
    int K = 1;
    System.out.println(countOfWays(S, K));
 
  }
 
}
 
// This code is contributed by _saurabh_jaiswal.

Python3

# Python program for the above approach
MOD = 1000000007
 
# Function to find the value of a^b
# modulo 1000000007
def exp_mod(a, b):
     
    # Stores the resultant value a^b
    ret = 1
     
    # Find the value of a^b
    while(b):
        if (b & 1):
            ret = ret * a % MOD
        b >>= 1
        a = a * a % MOD
     
    return ret
 
# Function to count the number of ways
# such that the formed number is divisible
# by 5 by removing digits
def countOfWays(s, k):
     
    N = len(s)
     
    # Stores the count of ways
    ans = 0
     
    # Find the count for string S
    for i in range(N):
         
        # If the digit is 5 or 0
        if (s[i] == '5' or s[i] == '0'):
            ans = (ans + exp_mod(2, i)) % MOD
             
    # Find the count of string for K
    # concatenation of string S
    q = exp_mod(2, N)
    qk = exp_mod(q, k)
    inv = exp_mod(q - 1, MOD - 2)
     
    # Find the total count
    ans = ans * (qk - 1) % MOD
    ans = ans * inv % MOD
     
    return ans
 
# Driver Code
S = "1256"
K = 1
print(countOfWays(S, K))
 
# This code is contributed by shivani

C#

// C# program for the above approach
using System;
 
public class GFG
{
  static long MOD = 1000000007;
 
  // Function to find the value of a^b
  // modulo 1000000007
  public static long exp_mod(long a, long b) {
 
    // Stores the resultant value a^b
    long ret = 1;
 
    // Find the value of a^b
    for (; b > 0; b >>= 1, a = a * a % MOD) {
      if ((b & 1) > 0)
        ret = ret * a % MOD;
    }
 
    return ret;
  }
 
  // Function to count the number of ways
  // such that the formed number is divisible
  // by 5 by removing digits
  public static long countOfWays(String s, int k) {
    int N = s.Length;
 
    // Stores the count of ways
    long ans = 0;
 
    // Find the count for string S
    for (int i = 0; i < N; i++) {
 
      // If the digit is 5 or 0
      if (s[i] == '5' || s[0] == '0') {
        ans = (ans + exp_mod(2, i)) % MOD;
      }
    }
 
    // Find the count of string for K
    // concatenation of string S
    long q = exp_mod(2, N);
    long qk = exp_mod(q, k);
    long inv = exp_mod(q - 1, MOD - 2);
 
    // Find the total count
    ans = ans * (qk - 1) % MOD;
    ans = ans * inv % MOD;
 
    return ans;
  }
 
  // Driver Code
  public static void Main(String []args) {
    String S = "1256";
    int K = 1;
    Console.WriteLine(countOfWays(S, K));
 
  }
 
}
 
// This code is contributed by shikhasingrajput

Javascript

// JavaScript program for the above approach
let MOD = 1000000007;
 
// Function to find the value of a^b
// modulo 1000000007
function exp_mod(a, b)
{
    a = BigInt(a);
    b = BigInt(b);
     
    // Stores the resultant value a^b
    let ret = 1n;
 
    // Find the value of a^b
    for (; b; b >>= 1n, a = a * a % BigInt(MOD)) {
        if (b & 1n)
            ret = ret * a % BigInt(MOD);
    }
 
    return parseInt(ret);
}
 
// Function to count the number of ways
// such that the formed number is divisible
// by 5 by removing digits
function countOfWays(s, k)
{
    let N = s.length;
 
    // Stores the count of ways
    let ans = 0;
    // Find the count for string S
    for (var i = 0; i < N; i++) {
        // If the digit is 5 or 0
        if (s[i] == '5' || s[i] == '0') {
             
            ans += (exp_mod(2, i)) % MOD;
            ans %= MOD;
        }
         
    }
 
    // Find the count of string for K
    // concatenation of string S
    let q = exp_mod(2, N);
    let qk = exp_mod(q, k);
    let inv = exp_mod(q - 1, MOD - 2);
 
    // Find the total count
    ans = (ans * (qk - 1)) % MOD;
    ans = (ans * inv) % MOD;
 
    return ans;
}
 
// Driver Code
let S = "1256";
let K = 1;
console.log(countOfWays(S, K));
 
// This code is contributed by phasing17
Producción: 

4

 

Complejidad de tiempo: O(N*log K)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *