Рубрики

Количество целых чисел из диапазона [0, N], сумма цифр которых кратна K

Для двух целых чисел N и K задача состоит в том, чтобы вычислить число целых чисел в диапазоне [0, N] , цифр которых кратен K. Ответ может быть большим, поэтому выведите ответ по модулю 10 9 +7 .

Примеры:

Input: N = 10, K = 5
Output: 2
0 and 5 are the only possible integers.

Input: N = 30, K = 4
Output: 7

Наивный подход: для небольшого значения N проведите цикл в диапазоне [0, N] и проверьте, является ли сумма цифр чисел кратной K или нет.

Эффективный подход: идея состоит в том, чтобы использовать цифру dp для решения этой проблемы. Подзадачи, выполняющие итерацию по всему значению индекса от левой или самой значимой цифры (MSD) в данном целом числе, будут решены, и для каждого индекса сохраните количество способов таким образом, чтобы (сумма цифр до текущего индекса) mod K была равна нулю. Состояния дп будут:

dp[idx][sum][tight]
idx = position, it tells about the index value from left in the given integer
sum = sum of digits mod k, This parameter will store the (sum of digits mod k) in the generated integer from most significant digit(MSD) to p
tight = flag if the current value is crossing the range (1, n) or not
For unrestricted range tight = 0
For restricted range tight = 1

Допустим, мы находимся в MSD с индексом idx . Поэтому изначально сумма будет 0 . В каждой позиции установите предел, который всегда находится в диапазоне [0, 9] .
Поэтому заполните цифру в индексе цифрами в диапазоне от 0 до предела и извлеките ответ из следующего состояния, имеющего index = idx + 1 и new_tight для следующего состояния, которое рассчитывается отдельно. Определение состояния dp будет:

dp[idx][sum][tight] += dp[idx + 1][(sum + d) % k][new_tight]
for d in [0, limit]

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
#define MAX 100005
#define MOD 1000000007

  
// Для хранения состояний дп

int dp[MAX][101][2];

  
// Функция для возврата количества чисел
// из диапазона [0, n], чья сумма цифр
// кратно k с использованием восходящего dp

int countNum(int idx, int sum, int tight,

             vector<int> num, int len, int k)

{

    if (len == idx) {

        if (sum == 0)

            return 1;

        else

            return 0;

    }

    if (dp[idx][sum][tight] != -1)

        return dp[idx][sum][tight];

    int res = 0, limit;

  

    // Цифра в этом индексе может

    // только из [0, num [idx]]

    if (tight == 0) {

        limit = num[idx];

    }

  

    // Цифра в этом индексе может

    // быть чем-нибудь из [0, 9]

    else {

        limit = 9;

    }

    for (int i = 0; i <= limit; i++) {

  

        // new_tight - значение флага

        // для следующей позиции

        int new_tight = tight;

        if (tight == 0 && i < limit)

            new_tight = 1;

        res += countNum(idx + 1,

                        (sum + i) % k, new_tight,

                        num, len, k);

        res %= MOD;

    }

  

    // res не может быть отрицательным

    if (res < 0)

        res += MOD;

    return dp[idx][sum][tight] = res;

}

  
// Функция для обработки строки
// вектор цифр из MSD в LSD

vector<int> process(string s)

{

    vector<int> num;

    for (int i = 0; i < s.length(); i++) {

        num.push_back(s[i] - '0');

    }

    return num;

}

  
// Код драйвера

int main()

{

  

    // Для большого числа ввода n

    string n = "98765432109876543210";

  

    // Общее количество цифр в n

    int len = n.length();

  

    int k = 58;

  

    // Очистим таблицу дп

    memset(dp, -1, sizeof(dp));

  

    // Обрабатываем строку в вектор

    // цифр от MSD до LSD

    vector<int> num = process(n);

  

    cout << countNum(0, 0, 0, num, len, k);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

{

  

static final int MAX = 100005;

static final int MOD = 1000000007;

  
// Для хранения состояний дп

static int [][][]dp = new int[MAX][101][2];

  
// Функция для возврата количества чисел
// из диапазона [0, n], чья сумма цифр
// кратно k с использованием восходящего dp

static int countNum(int idx, int sum, int tight,

            Vector<Integer> num, int len, int k)

{

    if (len == idx) 

    {

        if (sum == 0)

            return 1;

        else

            return 0;

    }

    if (dp[idx][sum][tight] != -1)

        return dp[idx][sum][tight];

    int res = 0, limit;

  

    // Цифра в этом индексе может

    // только из [0, num [idx]]

    if (tight == 0

    {

        limit = num.get(idx);

    }

  

    // Цифра в этом индексе может

    // быть чем-нибудь из [0, 9]

    else

    {

        limit = 9;

    }

    for (int i = 0; i <= limit; i++)

    {

  

        // new_tight - значение флага

        // для следующей позиции

        int new_tight = tight;

        if (tight == 0 && i < limit)

            new_tight = 1;

        res += countNum(idx + 1,

                        (sum + i) % k, new_tight,

                        num, len, k);

        res %= MOD;

    }

  

    // res не может быть отрицательным

    if (res < 0)

        res += MOD;

    return dp[idx][sum][tight] = res;

}

  
// Функция для обработки строки в
// вектор цифр из MSD в LSD

static Vector<Integer> process(String s)

{

    Vector<Integer> num = new Vector<Integer>();

    for (int i = 0; i < s.length(); i++)

    {

        num.add(s.charAt(i) - '0');

    }

    return num;

}

  
// Код драйвера

public static void main(String[] args)

{

  

    // Для большого числа ввода n

    String n = "98765432109876543210";

  

    // Общее количество цифр в n

    int len = n.length();

  

    int k = 58;

  

    // Очистим таблицу дп

    for(int i = 0; i < MAX; i++)

    {

        for(int j = 0; j < 101; j++)

        {

            for(int l = 0; l < 2; l++)

            dp[i][j][l] = -1;

        }

    }

  

    // Обрабатываем строку в вектор

    // цифр от MSD до LSD

    Vector<Integer> num = process(n);

  

    System.out.print(countNum(0, 0, 0, num, len, k));

  
}
}

  
// Этот код предоставлен 29AjayKumar

Python 3

# Python 3 реализация подхода

MAX = 10005

MOD = 1000000007

  
# Функция для возврата количества чисел
# из диапазона [0, n], чья сумма цифр
# является кратным k, используя дп снизу вверх

def countNum(idx, sum, tight, num, len1, k):

    if (len1 == idx):

        if (sum == 0):

            return 1

        else:

            return 0

    if (dp[idx][sum][tight] != -1):

        return dp[idx][sum][tight]

    res = 0

  

    # Цифра в этом индексе может

    # только из [0, num [idx]]

    if (tight == 0):

        limit = num[idx]

  

    # Цифра в этом индексе может

    # быть чем-нибудь из [0, 9]

    else:

        limit = 9

    for i in range(limit + 1):

          

        # new_tight - значение флага

        # для следующей позиции

        new_tight = tight

        if (tight == 0 and i < limit):

            new_tight = 1

        res += countNum(idx + 1,(sum + i) % k, 

                      new_tight, num, len1, k)

        res %= MOD

  

    # res не может быть отрицательным

    if (res < 0):

        res += MOD

    dp[idx][sum][tight] = res

    return dp[idx][sum][tight]

  
# Функция для обработки строки
# вектор цифр от MSD до LSD

def process(s):

    num = []

    for i in range(len(s)):

        num.append(ord(s[i]) - ord('0'))

    return num

  
# Код драйвера

if __name__ == '__main__':

      

    # Для большого числа ввода n

    n = "98765432109876543210"

  

    # Общее количество цифр в n

    len1 = len(n)

  

    k = 58

      

    # Для хранения состояний дп

    dp = [[[-1 for i in range(2)]

               for j in range(101)] 

               for k in range(MAX)]

  

    # Обработка строки в вектор

    Количество цифр от MSD до LSD

    num = process(n)

  

    print(countNum(0, 0, 0, num, len1, k))

  
# Этот код предоставлен Surendra_Gangwar

C #

// C # реализация подхода

using System;

using System.Collections.Generic;

  

class GFG

{

static readonly int MAX = 10005;

static readonly int MOD = 1000000007;

  
// Для хранения состояний дп

static int [,,]dp = new int[MAX, 101, 2];

  
// Функция для возврата количества чисел
// из диапазона [0, n], чья сумма цифр
// кратно k с использованием восходящего dp

static int countNum(int idx, int sum, int tight,

              List<int> num, int len, int k)

{

    if (len == idx) 

    {

        if (sum == 0)

            return 1;

        else

            return 0;

    }

      

    if (dp[idx, sum, tight] != -1)

        return dp[idx, sum, tight];

    int res = 0, limit;

  

    // Цифра в этом индексе может

    // только из [0, num [idx]]

    if (tight == 0) 

    {

        limit = num[idx];

    }

  

    // Цифра в этом индексе может

    // быть чем-нибудь из [0, 9]

    else

    {

        limit = 9;

    }

    for (int i = 0; i <= limit; i++)

    {

  

        // new_tight - значение флага

        // для следующей позиции

        int new_tight = tight;

        if (tight == 0 && i < limit)

            new_tight = 1;

        res += countNum(idx + 1,

                       (sum + i) % k, new_tight,

                        num, len, k);

        res %= MOD;

    }

  

    // res не может быть отрицательным

    if (res < 0)

        res += MOD;

    return dp[idx, sum, tight] = res;

}

  
// Функция для обработки строки в
// вектор цифр из MSD в LSD

static List<int> process(String s)

{

    List<int> num = new List<int>();

    for (int i = 0; i < s.Length; i++)

    {

        num.Add(s[i] - '0');

    }

    return num;

}

  
// Код драйвера

public static void Main(String[] args)

{

  

    // Для большого числа ввода n

    String n = "98765432109876543210";

  

    // Общее количество цифр в n

    int len = n.Length;

  

    int k = 58;

  

    // Очистим таблицу дп

    for(int i = 0; i < MAX; i++)

    {

        for(int j = 0; j < 101; j++)

        {

            for(int l = 0; l < 2; l++)

            dp[i, j, l] = -1;

        }

    }

  

    // Обрабатываем строку в вектор

    // цифр от MSD до LSD

    List<int> num = process(n);

  

    Console.Write(countNum(0, 0, 0, num, len, k));

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

635270835

Рекомендуемые посты:

Количество целых чисел из диапазона [0, N], сумма цифр которых кратна K

0.00 (0%) 0 votes