Подсчитайте числа из N цифр, суффикс которых делится на K
Учитывая два натуральных числа 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 РЕКОМЕНДУЕМЫЕ СТАТЬИ |