Подсчитайте числа из N цифр, суффикс которых делится на K

Опубликовано: 7 Января, 2022

Учитывая два натуральных числа N и K , задача состоит в том, чтобы подсчитать количество таких положительных чисел D , что D имеет N цифр и любой суффикс его десятичного представления делится на K.
Примеры:

Input: N = 1, K = 2
Output: 4
Explanation:
There are 4 such integers in which any of the suffix is divisible by K:
{2, 4, 6, 8}

Input: N = 2, K = 2
Output: 45
Explanation:
There are 45, Two digit integers in which any of the suffix is divisible by 2:
Some of such integers is given below –
{10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23…}
Notice that, 21 and 23 numbers are not divisible by 2. But their suffix 2 is divisible by 2.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: переберите все целые числа из N цифры и для каждого целого числа проверьте, что любой суффикс числа делится на K, если да, то увеличьте количество таких чисел на 1.

Подход: идея состоит в том, чтобы использовать концепцию динамического программирования путем увеличения длины суффикса и повторного размещения цифр от 0 до 9. Ниже представлена иллюстрация шагов:

  • Определение функции: эта проблема может быть решена рекурсивно, в котором на каждом шаге мы можем выбирать цифры для суффикса для N-значного числа. Итак, определение функции рекурсивного решения будет:
    // Рекурсивная функция для подсчета значений
// чьи суффиксы длины pos 
// имеем остаток rem с K
повторять (pos, rem)
  • Базовый случай: базовый случай для этой проблемы - когда для любого индекса остаток суффикса с K становится 0, тогда все другие цифры могут быть помещены со всеми возможными целыми числами от 0 до 9.
    f (pos, 0) = 9 * (10 ^ (ni-1))
  • Рекурсивный случай: на каждом шаге рекурсии мы увеличиваем длину суффикса на единицу, помещая все целые числа от 0 до 9, соответственно меняем остаток с помощью K и переходим к следующему шагу.
    для числа в диапазоне [0-9]:
     f (pos, rem) + = f (pos + 1, (rem * 10 + num)% k)

Below is the implemenation of the above approach:

C++

// C++ implementation to Count the 
// numbers with N digits and whose 
// suffix is divisible by K
  
#include <bits/stdc++.h>
  
using namespace std;
  
int mod = 1000000007;
int dp[1005][105][2];
int powers[1005];
int powersModk[1005];
  
// Suffix of length pos with 
// remainder rem and Z representing
// whether the suffix has a 
// non zero digit until now
int calculate(int pos, int rem, 
           int z, int k, int n)
{
    // Base case
    if (rem == 0 && z) {
          
        // If count of digits 
        // is less than n
        if (pos != n)
              
            // Placing all possible 
            // digits in remaining 
            // positions
            return (powers[n - pos - 
                        1] * 9) % mod;
        else
            return 1;
    }
      
    // If remainder non zero 
    // and suffix has n digits
    if (pos == n)
        return 0;
      
    // If the subproblem 
    // is already solved
    if (dp[pos][rem][z] != -1)
        return dp[pos][rem][z];
  
    int count = 0;
  
    // Placing all digits at MSB 
    // of suffix and increasing 
    // it"s length by 1
    for (int i = 0; i < 10; i++) {
        if (i == 0)
            count = (count + (calculate(
             pos + 1, (rem + (i * 
                 powersModk[pos]) % k) % 
                    k, z, k, n))) % mod;
  
        // Non zero digit is placed
        else
            count = (count + (calculate(
                pos + 1, (rem + (i * 
                powersModk[pos]) % k) % 
                k, 1, k, n))) % mod;
    }
  
    // Store and return the 
    // solution to this subproblem
    return dp[pos][rem][z] = count;
}
  
// Function to Count the numbers 
// with N digits and whose suffix 
// is divisible by K
int countNumbers(int n, int k)
{
  
    // Since we need powers of 10 
    // for counting, it"s better to 
    // pre store them along with their 
    // modulo with 1e9 + 7 for counting
    int st = 1;
    for (int i = 0; i <= n; i++) {
        powers[i] = st;
        st *= 10;
        st %= mod;
    }
  
    // Since at each recursive step 
    // we increase the suffix length by 1
    // by placing digits at its leftmost 
    // position, we need powers of 10
    // modded with k, in order to fpos 
    // the new remainder efficiently
    st = 1;
    for (int i = 0; i <= n; i++) {
        powersModk[i] = st;
        st *= 10;
        st %= mod;
    }
  
    // Initialising dp table values -1
    // represents subproblem hasn"t 
    // been solved yet
    memset(dp, -1, sizeof(dp));
  
    return calculate(0, 0, 0, k, n);
}
  
// Driver Code
int main()
{
    int N = 2;
    int K = 2;
  
    cout << countNumbers(N, K);
  
    return 0;
}

Java

// Java implementation to Count the 
// numbers with N digits and whose 
// suffix is divisible by K
import java.util.*;
import java.util.Arrays;
  
class GFG
{
      
    static int mod = 1000000007;
    static int dp[][][] = new int[1005][105][2];
    static int powers[] = new int[1005];
    static int powersModk[] = new int[1005];
      
    // Suffix of length pos with 
    // remainder rem and Z representing
    // whether the suffix has a 
    // non zero digit until now
    static int calculate(int pos, int rem, 
            int z, int k, int n)
    {
        // Base case
        if (rem == 0 && z!=0) {
              
            // If count of digits 
            // is less than n
            if (pos != n)
                  
                // Placing all possible 
                // digits in remaining 
                // positions
                return (powers[n - pos - 
                            1] * 9) % mod;
            else
                return 1;
        }
          
        // If remainder non zero 
        // and suffix has n digits
        if (pos == n)
            return 0;
          
        // If the subproblem 
        // is already solved
        if (dp[pos][rem][z] != -1)
            return dp[pos][rem][z];
      
        int count = 0;
      
        // Placing all digits at MSB 
        // of suffix and increasing 
        // it"s length by 1
        for (int i = 0; i < 10; i++) {
            if (i == 0)
                count = (count + (calculate(
                pos + 1, (rem + (i * 
                    powersModk[pos]) % k) % 
                        k, z, k, n))) % mod;
      
            // Non zero digit is placed
            else
                count = (count + (calculate(
                    pos + 1, (rem + (i * 
                    powersModk[pos]) % k) % 
                    k, 1, k, n))) % mod;
        }
      
        // Store and return the 
        // solution to this subproblem
        return dp[pos][rem][z] = count;
    }
      
    // Function to Count the numbers 
    // with N digits and whose suffix 
    // is divisible by K
    static int countNumbers(int n, int k)
    {
      
        // Since we need powers of 10 
        // for counting, it"s better to 
        // pre store them along with their 
        // modulo with 1e9 + 7 for counting
        int st = 1;
        int i;
        for (i = 0; i <= n; i++) {
            powers[i] = st;
            st *= 10;
            st %= mod;
        }
      
        // Since at each recursive step 
        // we increase the suffix length by 1
        // by placing digits at its leftmost 
        // position, we need powers of 10
        // modded with k, in order to fpos 
        // the new remainder efficiently
        st = 1;
        for (i = 0; i <= n; i++) {
            powersModk[i] = st;
            st *= 10;
            st %= mod;
        }
      
        // Initialising dp table values -1
        // represents subproblem hasn"t 
        // been solved yet
        for (int[][] row: dp)
        {
            for (int[] innerRow: row)
            {
                Arrays.fill(innerRow, -1);
            }
        };
      
        return calculate(0, 0, 0, k, n);
    }
  
    // Driver Code
    public static void main(String []args)
    {
        int N = 2;
        int K = 2;
      
        System.out.print(countNumbers(N, K));
    }
}
  
// This code is contributed by chitranayal

Python3

# Python3 implementation to Count the
# numbers with N digits and whose
# suffix is divisible by K
  
mod = 1000000007
dp = [[[-1 for i in range(2)] for i in range(105)] for i in range(1005)]
powers = [0]*1005
powersModk = [0]*1005
  
# Suffix of length pos with
# remainder rem and Z representing
# whether the suffix has a
# non zero digit until now
def calculate(pos, rem, z, k, n):
    # Base case
    if (rem == 0 and z):
  
        # If count of digits
        # is less than n
        if (pos != n):
  
            # Placing all possible
            # digits in remaining
            # positions
            return (powers[n - pos -1] * 9) % mod
        else:
            return 1
  
    # If remainder non zero
    # and suffix has n digits
    if (pos == n):
        return 0
  
    # If the subproblem
    # is already solved
    if (dp[pos][rem][z] != -1):
        return dp[pos][rem][z]
  
    count = 0
  
    # Placing all digits at MSB
    # of suffix and increasing
    # it"s length by 1
    for i in range(10):
        if (i == 0):
            count = (count + (calculate(
            pos + 1, (rem + (i *
                powersModk[pos]) % k) %
                    k, z, k, n))) % mod
  
        # Non zero digit is placed
        else:
            count = (count + (calculate(
                pos + 1, (rem + (i *
                powersModk[pos]) % k) %
                k, 1, k, n))) % mod
  
    # Store and return the
    # solution to this subproblem
    dp[pos][rem][z] = count
    return count
  
# Function to Count the numbers
# with N digits and whose suffix
# is divisible by K
def countNumbers(n, k):
  
    # Since we need powers of 10
    # for counting, it"s better to
    # pre store them along with their
    # modulo with 1e9 + 7 for counting
    st = 1
    for i in range(n + 1):
        powers[i] = st
        st *= 10
        st %= mod
  
    # Since at each recursive step
    # we increase the suffix length by 1
    # by placing digits at its leftmost
    # position, we need powers of 10
    # modded with k, in order to fpos
    # the new remainder efficiently
    st = 1
    for i in range(n + 1):
        powersModk[i] = st
Олимпиады по программированию Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Настройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022