242.

Digit DP

1
 Table of Contents

Assignment Question 1 – Find Magic Numbers.....................................................................................4

Assignment Question 2 – Non Zero Digits.............................................................................................6
Assignment Question 3 – Playing among Digits.....................................................................................8
Additional Problems 1 – Palindromic Beauty.......................................................................................10
Additional Problems 2 – Double Sum..................................................................................................12
Additional Problems 3 – Jesse and Maths...........................................................................................14
Assignment Question 1 – Find Magic Numbers...................................................................................16
Hint:.................................................................................................................................................16
Solution Approach:..........................................................................................................................16
Complete Solution: C++...................................................................................................................17
Complete Solution: Python..............................................................................................................19
Complete Solution: Java...................................................................................................................21
Assignment Question 2 – Non Zero Digits...........................................................................................23
Hint:.................................................................................................................................................23
Solution Approach:..........................................................................................................................23
Complete Solution: C++...................................................................................................................24
Complete Solution: Python..............................................................................................................25
Complete Solution: Java...................................................................................................................26
Assignment Question 3 – Playing among Digits...................................................................................27
Hint:.................................................................................................................................................27
Solution Approach:..........................................................................................................................27
Complete Solution: C++...................................................................................................................28
Complete Solution: Java...................................................................................................................30
Additional Problems 1 – Palindromic Beauty.......................................................................................32
Hint:.................................................................................................................................................32
Solution Approach:..........................................................................................................................32
Complete Solution: C++...................................................................................................................33
Complete Solution: Python..............................................................................................................34
Complete Solution: Java...................................................................................................................36
Additional Problems 2 – Double Sum..................................................................................................38
Hint:.................................................................................................................................................38
Solution Approach:..........................................................................................................................38
Complete Solution: C++...................................................................................................................39

2
 Complete Solution: Python..............................................................................................................40
Complete Solution: Java...................................................................................................................41
Additional Problems 3 – Jesse and Maths...........................................................................................42
Hint:.................................................................................................................................................42
Solution Approach:..........................................................................................................................42
Complete Solution: C++...................................................................................................................43
Complete Solution: Python..............................................................................................................44
Complete Solution: Java...................................................................................................................46
Assignment Question 1 – Find Magic Numbers – Solution..................................................................48
Assignment Question 2 – Non Zero Digits – Solution...........................................................................50
Assignment Question 3 – Playing among Digits – Solution..................................................................52
Additional Problems 1 – Palindromic Beauty – Solution......................................................................54
Additional Problems 2 – Double Sum – Solution.................................................................................56
Additional Problems 3 – Jesse and Maths – Solution...........................................................................58

3
Assignment Question 1 – Find Magic Numbers
Problem Description

Consider the decimal presentation of an integer. Let's call a number D - magic if

digit D appears in decimal presentation of the number on all even positions and nowhere
else.

For example, the numbers 1727374, 17, 1 are 7 - magic but 77, 7, 123, 34, 71 are not 7 -
magic.

On the other hand the number 7 is 0 - magic, 123 is 2 - magic, 34 is 4 - magic and 71 is 1 -
magic.

Find the number of D - magic numbers in the segment [L, R] that are multiple of C.
Because the answer can be very huge you should only find its value modulo 109 + 7 (so you
should find the remainder after dividing by 109 + 7).

Problem Constraints

1 <= C <= 2000

0 <= D <= 9

It is guaranteed that A <= B, the number of digits in A and B are the same and don't exceed
2000.

Input Format

First argument is an numeric string A denoting the positive integer L. (Without Leading
Zeroes).

Second argument is an numeric string B denoting the positive integer R. (Without Leading
Zeroes).

Third argument is an integer C.

Fourth argument is an integer D.

4
Output Format

Return an integer denoting the number of D - magic numbers in the segment [L, R] that
are multiple of C. Because the answer can be very huge you should only find its value
modulo 109 + 7 (so you should find the remainder after dividing by 109 + 7).

Example Input

Input 1:

A = "10"
B = "99"
C = 2
D = 6

Input 2:

A = "1000"
B = "9999"
C = 19
D = 7

Example Output

Output 1:

Output 2:

5
Example Explanation

Explanation 1:

The numbers from the answer of the first example are 16, 26,
36, 46, 56, 76, 86 and 96.

Explanation 2:

The numbers from the answer of the second example are 1767,
2717, 5757, 6707, 8797 and 9747.

Expected Output

Provide sample input and click run to see the correct output for the provided input. Use
this to improve your problem understanding and test edge cases

Arg 1: A single String, For e.g 'anagram'

Arg 2: A single String, For e.g 'anagram'
Arg 3: A single Integer, For e.g 9
Arg 4: A single Integer, For e.g 9

6
Assignment Question 2 – Non Zero Digits
Problem Description

Nobita's teacher gave him some problems to solve.

He has to solve q queries. He is given a list A of strings. List A contains numbers in string
format. The ith query consists of numbers A[2*i] and A[2*i+1]. The answer to ith query is the
count from A[2*i] to A[2*i+1] whose decimal representation contains no more than 3 non-
zero digits. Since the answer can be large, return it modulo 109 + 7.

Can you help him?

Problem Constraints

2 <= |A| <= 2*104

|A| is even

1 <= |A[i]| <= 18

A[i] does not contain leading zeroes

Input Format

The first line of input contains A- list of numbers in string format.

Output Format

Return a vector of size q- ith of which contains the answer for ith query.

7
Example Input

Input 1:

["1", "10"]

Input 2:

["1109", "1115"]

Example Output

Output 1:

10

Output 2:

Example Explanation

Explanation 1:

All numbers have less than or equal to 3 non-zero digits.

Explanation 2:

The valid numbers are- 1109, 1110.

Expected Output

Provide sample input and click run to see the correct output for the provided input. Use
this to improve your problem understanding and test edge cases

Arg 1: A String Array, For e.g ['hello','world']

8
Assignment Question 3 – Playing among Digits
Problem Description

Determine the number of integers that are available from L to R (both inclusive) and
satisfy the following conditions:

 Sum of its digits is equal to a prime number

 Divisible by C

Please try to use any fast language to solve this proble like C++, Java etc. (not
Python)

Problem Constraints

1 <= L, R, C <= 2 × 1010

It is guaranteed that A <= B, the number of digits in A and B don't exceed 11.

Input Format

First argument is an numeric string A denoting the integer L.

Second argument is an numeric string B denoting the integer R.

Third argument is an integer C.

NOTE: A and B doesn't contain leading zeroes and 1 <= |A|, |B| <= 11

Output Format

Return a single integer that denotes the answer to this question modulo 109 + 7

9
Example Input

Input 1:

A = "5"
B = "86"
C = 4

Input 2:

A = "1"
B = "20"
C = 2

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1:

There are 7 such numbers: 12 16 20 32 52 56 76

Expected Output

Provide sample input and click run to see the correct output for the provided input. Use
this to improve your problem understanding and test edge cases

Arg 1: A single String, For e.g 'anagram'

Arg 2: A single String, For e.g 'anagram'
Arg 3: A single Integer, For e.g 9

10
Additional Problems 1 – Palindromic Beauty
Problem Description

The palindromic beauty of a set of numbers is the number of palindromes in a set. A

number is a palindrome that remains the same when its digits are reversed. The number
should be considered without leading zeroes.

You have to solve q queries. You are given a list A of strings. List A contains numbers in
string format. The ith query consists of numbers A[2*i] and A[2*i+1]. The answer to ith query
is the palindromic beauty of set of numbers from A[2*i] to A[2*i+1]. Since the answer can
be large, return it modulo 109 + 7.

Problem Constraints

2 <= |A| <= 400

|A| is even

1 <= |A[i]| <= 17

A[i] does not contain leading zeroes

Input Format

The first line of input contains A- list of numbers in string format.

Output Format

Return a vector of size q- ith of which contains the answer for ith query.

Example Input

Input 1:

A = ["1", "5", "7", "12"]

Input 2:

A = ["1", "100"]

11
Example Output

Output 1:

[5, 4]

Output 2:

18

Example Explanation

Explanation 1:

In the first query, all numbers from 1 to 5 are palindromes.

In the second query, 7, 8, 9 and 11 are palindromes.

Explanation 2:

Palindromes in the range are-

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88,
99

Expected Output

Provide sample input and click run to see the correct output for the provided input. Use
this to improve your problem understanding and test edge cases

Arg 1: A String Array, For e.g ['hello','world']

12
Additional Problems 2 – Double Sum
Problem Description

Digit sum of a number is the sum of digits of a number.

You have to solve q queries. You are given a list A of strings. List A contains numbers in
string format. The ith query consists of numbers A[2*i] and A[2*i+1]. The answer to ith query
is the digit sum of set of numbers from A[2*i] to A[2*i+1]. Since the answer can be large,
return it modulo 109 + 7.

Problem Constraints

2 <= |A| <= 200

|A| is even

1 <= |A[i]| <= 15

A[i] does not contain leading zeroes.

Input Format

The first line of input contains A- list of numbers in string format.

Output Format

Return a vector of size q- ith of which contains the answer for ith query.

Example Input

Input 1:

["1", "5", "22", "23"]

Input 2:

["10", "15"]

13
Example Output

Output 1:

[15, 9]

Output 2:

[21]

Example Explanation

Explanation 1:

For first query, 1 + 2 + 3 + 4 + 5 = 15.

For second query, 2 + 2 + 2 + 3 = 9.

Explanation 2:

1 + 0 + 1 + 1 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 = 21

Expected Output

Provide sample input and click run to see the correct output for the provided input. Use
this to improve your problem understanding and test edge cases

Arg 1: A String Array, For e.g ['hello','world']

14
Additional Problems 3 – Jesse and Maths
Problem Description

Jesse likes to go to math clubs. These are the places where like-minded people, interested
in mathematics, discuss several problem solving tecniques.

Today, looking at the progress of Jesse, his friend decides to challenge him with a hard
problem in the club.

He gives Jesse a number n and asks to determine, number of pairs (x, y) such that:

 S(x) < S(y) where S(k) denotes the sum of digits of integer k.
 0 <= x < y <= n

Can you help Jesse find the answer?

Problem Constraints

1 <= n <= 10250

Input Format

First and only argument is an numeric string A denoting the integer n.

NOTE: A doesn't contain leading zeroes.

Output Format

Return the number of pairs, that satisfy the above property modulo 109 + 7 .

15
Example Input

Input 1:

A = "3"

Input 2:

A = "67535"

Example Output

Output 1:

Output 2:

358739816

Example Explanation

Explanation 1:

The number of valid pairs such that 0 <= x < y <= 3 and S(x)
< S(y) are (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3).
Therefore, the output is 6.

Expected Output

Provide sample input and click run to see the correct output for the provided input. Use
this to improve your problem understanding and test edge cases

Arg 1: A single String, For e.g 'anagram'

16
Assignment Question 1 – Find Magic Numbers
Hint:
Denote the answer to the problem f(a, b). Note that f(a, b) = f(0, b) - f(0, a - 1) or what is the same
f(a, b) = f(0, b) - f(0, a) + g(a), where g(a) equals to one if a is a magic number, otherwise g(a)
equals to zero.
Let’s solve the problem for the segment [0, n].

Solution Approach:

Denote the answer to the problem f(a, b). Note that f(a, b) = f(0, b) - f(0, a - 1) or what is
the same f(a, b) = f(0, b) - f(0, a) + g(a), where g(a) equals to one if a is a magic number,
otherwise g(a) equals to zero. Let’s solve the problem for the segment [0, n].

Here is described the standard technique for this kind of problems, sometimes it is
called ‘dynamic programming by digits’. It can be realized in a two ways.

The first way is to iterate over the length of the common prefix with number n. Next digit
should be less than corresponding digit in n and other digits can be arbitrary.

Below is the description of the second approach.

Let zijk be the number of magic prefixes of length i with remainder j modulo m. If k = 0
than the prefix should be less than the corresponding prefix in n and if k = 1 than the
prefix should be equal to the prefix of n (it cannot be greater).

Let’s do ‘forward dynamic programming’. Let’s iterate over digit p = [0…9] in position i.

We should check that if the position is even than p should be equal to d, otherwise it
cannot be equal to d.

Also, we should check for k = 1 p should be not greater than corresponding digit in n.

Now let’s see what will be the next state. Of course, i’ = i + 1. By Horner scheme j’ = 10j +
p) mod m.

Easy to see that k’ = l ^ [ p = n i]. To update the next state, we should increase it: z i’j’k’ += zijk.
Of course, all calculations should be done modulo 10 9 + 7.

Time Complexity: O(C×B)

Space Complexity: O(C×B)

17
Complete Solution: C++

#define pb push_back
#define ll long long
const int mod = 1000000007;
const int sizee = 2005;
int dp[sizee][sizee][2];
vector < int > v;

int memo(int index, int rem, int tight, int d, int m) {

if (index == [Link]()) {
if (rem == 0) return 1;
return 0;
}

if (dp[index][rem][tight] != -1) return dp[index][rem][tight];

if (index % 2) {
if (tight == 0 && d > v[index]) return 0;

int currTight = tight;

if (d < v[index]) currTight = 1;

int newRem = (10 * rem + d) % m;

ll res = memo(index + 1, newRem, currTight, d, m);
res %= mod;
return dp[index][rem][tight] = res;
}

ll ans = 0 ;
int limit = (tight ? 9 : v[index]);
for (int i = 0; i <= limit; i++) {
if (i == d) continue;

int currTight = tight;

if (i < v[index]) currTight = 1;

int newRem = (10 * rem + i) % m;
ans += memo(index + 1, newRem, currTight, d, m);
ans = ans % mod;
}

ans %= mod;
return dp[index][rem][tight] = ans;
}

int solveQ(string n, int d, int m) {

[Link]();

for (int i = 0; i < [Link](); i++) {

int temp = n[i] - '0';
[Link](temp);
}

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

int ans = memo(0, 0, 0, d, m);
return ans;
}

18
int Solution::solve(string A, string B, int C, int D) {
string l = A;
string r = B;
int m = C;
int d = D;
assert(m >= 1 && m <= 2000);
assert(d >= 0 && d < 10);
assert([Link]() == [Link]() && [Link]() <= 2000 && [Link]() >= 1);

for (int i = [Link]() - 1;; i--) {

if (l[i] == '0') l[i] = '9';
else {
l[i]--;
break;
}
}

ll right = solveQ(r, d, m);

ll left = solveQ(l, d, m);
ll ans = (right - left + mod) % mod;

return ans;
}

19
Complete Solution: Python

import sys

mod = 10 ** 9 + 7

def solvee(a, m, d):

dp = [0] * m
border = a[0] % m if a[0] != d else -1
m10 = 10 % m

for i in range(a[0]):
if i != d:
dp[i % m] += 1

for i, digit in enumerate(a[1:], start=1):

next_dp = [0] * m

if i & 1:
t = d % m

for j in range(m):
next_dp[t] += dp[j]
t = t + m10 if t + m10 < m else t + m10 - m

if border != -1:
if d < digit:
next_dp[(border * 10 + d) % m] += 1
border = -1
elif d == digit:
border = (border * 10 + d) % m
else:
border = -1
else:
for j in range(m):
if dp[j] == 0:
continue

if dp[j] >= mod:

dp[j] -= mod

t = (j * 10 - 1) % m

for k in range(10):
t += 1

if t == m:
t = 0

if k == d:
continue

next_dp[t] += dp[j]

if next_dp[t] >= mod:

next_dp[t] -= mod

20
 if border != -1:
for k in range(digit):
if k == d:
continue
next_dp[(border * 10 + k) % m] += 1
if digit != d:
border = (border * 10 + digit) % m
else:
border = -1

dp = next_dp

return dp[0] + (1 if border == 0 else 0)

class Solution:
# @param A : string
# @param B : string
# @param C : integer
# @param D : integer
# @return an integer

def solve(self, A, B, C, D):

a = list(map(int, A))
b = list(map(int, B))
m = C
d = D
a[-1] -= 1

for i in range(len(a) - 1, 0, -1):

if a[i] < 0:
a[i] = 9
a[i - 1] -= 1
else:
break

ans = solvee(b, m, d) - solvee(a, m, d)

return ans % mod

21
Complete Solution: Java

public class Solution {

static final int MOD = (int) 1e9 + 7;

static int memo[][][][];

static int pow[];
static int m, d;
static char[] digits;
static char[] digits1;

static int dp(int pos, int less, int greater, int div) {
if (pos == [Link])
return div == 0 ? 1 : 0;

if (memo[less][greater][pos][div] != -1)
return memo[less][greater][pos][div];

long ans = 0;
int LIMIT = (less == 1 ? 9 : digits[pos] - '0'), start = (greater == 1
? 0 : digits1[pos] - '0');

for (int i = start; i <= LIMIT; i++)

if ((pos % 2 == 0 && i != d) || (pos % 2 == 1 && i == d))
ans = (long) add((int) ans, dp(pos + 1, less | (i < LIMIT ? 1 :
0), greater | (start < i ? 1 : 0), add(div, mult(i, pow[pos], m), m)),
MOD);

return memo[less][greater][pos][div] = (int) ans;

}

static int mult(int x, int y, int MOD) {

return (int)((1l * x * y) % MOD);
}

static int add(int x, int y, int MOD) {

int ans = x + y;

return ans % MOD;

}

static int modPow(int a, int e, int MOD) {

int res = 1;

while (e > 0) {
if ((e & 1) == 1)
res = mult(res, a, MOD);

a = mult(a, a, MOD);

e >>= 1;
}

return res;
}

22
 static void init() {
for (int[][][] x: memo)
for (int[][] xx: x)
for (int[] xxx: xx)
[Link](xxx, -1);

}
public int solve(String A, String B, int C, int D) {
m = C;
d = D;

String a = A;
String b = B;

memo = new int[2][2][[Link]()][m];

pow = new int[[Link]()];

for (int i = 0; i < [Link]; i++)

pow[i] = modPow(10, [Link] - i - 1, m);

init();
digits = [Link]();
digits1 = [Link]();

return (dp(0, 0, 0, 0));

}
}

23
Assignment Question 2 – Non Zero Digits
Hint:

Breaking the query from a to b to 0 to b and 0 to a - 1.

How to solve it for [0,n].

What states would we store?

We can keep a count of non zero digits but how to ensure the number is less than n?

Solution Approach:

Let’s use Digit Dp to solve it.

We have to solve it for 0 to A.

Let’s keep the current index at which we are placing a number, the flag to denote if we
have placed a smaller number previously and the count of non zero digits.

Now, we just have to handle cases of what would happen when we place non zero digits.

Time Complexity: O(A)

Space Complexity: O(A)

24
Complete Solution: C++

#define ll long long

const int mod = 1e9 + 7, N = 20;
ll dp[N][3][2];
ll solve(ll idx, ll non_zero, ll tight, string & s) {
if (idx == [Link]()) {
return 1;
}
if (non_zero == 3) {
return 1;
}
if (dp[idx][non_zero][tight] != -1) {
return dp[idx][non_zero][tight];
}
if (tight == 0) {
dp[idx][non_zero][tight] = (9 * solve(idx + 1, non_zero + 1, tight, s)
+ solve(idx + 1, non_zero, tight, s)) % mod;
} else {
ll dig = s[idx] - '0';
if (dig == 0) {
dp[idx][non_zero][tight] = solve(idx + 1, non_zero, tight, s);
} else {
dp[idx][non_zero][tight] = (solve(idx + 1, non_zero, (tight ^ 1), s)
+ (dig - 1) * solve(idx + 1, non_zero + 1, (tight ^ 1), s) + solve(idx +
1, non_zero + 1, tight, s)) % mod;
}
}
return dp[idx][non_zero][tight];
}
ll helper(string s) {
memset(dp, -1, sizeof dp);
return solve(0, 0, 1, s);
}

vector < int > Solution::solve(vector < string > & A) {

vector < int > ans;
for (int i = 0; i < [Link](); i += 2) {
ll l, r, diff;

string s1 = to_string(stoll(A[i]) - 1);

string s2 = A[i + 1];

l = helper(s1);
r = helper(s2);
diff = (r - l + mod) % mod;
ans.push_back(diff);
}
return ans;
}

25
Complete Solution: Python

import bisect

a = []
flag = 0

def preproc(pos, notnul, cur):

if pos == 18:
[Link](cur)
else:
preproc(pos + 1, notnul, cur * 10)
if notnul < 3:
for i in range(1, 10):
preproc(pos + 1, notnul + 1, cur * 10 + i)

class Solution:
# @param A : list of strings
# @return a list of integers
def solve(self, A):
global a, flag
if flag == 0:
preproc(0, 0, 0)
flag = 1
[Link](1000000000000000000)
n = len(A) // 2
ret = []
for i in range(n):
l, r = A[2 * i], A[2 * i + 1]
[Link](
bisect.bisect_right(a, int(r), 0, len(a))
- bisect.bisect_left(a, int(l), 0, len(a))
)
return ret

26
Complete Solution: Java

public class Solution {

final long mod = (int) 1e9 + 7;
long[][][] dp = new long[20][3][2];
public long solve(int idx, int non_zero, int tight, String s) {
if (idx == [Link]()) {
return 1;
}
if (non_zero == 3) {
return 1;
}
if (dp[idx][non_zero][tight] != -1) {
return dp[idx][non_zero][tight];
}
if (tight == 0) {
dp[idx][non_zero][tight] = (9 * solve(idx + 1, non_zero + 1, tight,
s) + solve(idx + 1, non_zero, tight, s)) % mod;
} else {
int dig = (int)([Link](idx) - '0');
if (dig == 0) {
dp[idx][non_zero][tight] = solve(idx + 1, non_zero, tight, s);
} else {
dp[idx][non_zero][tight] = (solve(idx + 1, non_zero, (tight ^ 1),
s) + (dig - 1) * solve(idx + 1, non_zero + 1, (tight ^ 1), s) + solve(idx
+ 1, non_zero + 1, tight, s)) % mod;
}
}
return dp[idx][non_zero][tight];
}
public long helper(String s) {
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 2; k++) {
dp[i][j][k] = -1;
}
}
}
return solve(0, 0, 1, s);
}
public int[] solve(String[] A) {
int[] ans = new int[[Link] / 2];
for (int i = 0; i < [Link]; i += 2) {
long l, r, left, right, diff = 0;
l = [Link](A[i]);
r = [Link](A[i + 1]);

left = helper([Link](l - 1));

right = helper([Link](r));

diff = (right - left + mod) % mod;

ans[i / 2] = (int) diff;

}

return ans;
}
}

27
Assignment Question 3 – Playing among Digits
Hint:

Think of using digit dp.

If C is greater than certain number can we find the answer without digit dp?

Try to use above facts to find a solution to the problem.

Solution Approach:
Pre-requisite: Digit-DP

The main observation here is C goes upto 2×10 10 so you can’t create a digit-dp table for all values
of C so you have to observe that whenever C>1000 the number of factors of C upto 2×10 10 will be
(2×1010/C) which will be less than 10 7 so this will run in 1 sec with simple brute-force approach
but whenever k is small its factors are more so here you will have to make a digit-dp table.

So first learn digit-dp if you don’t know and then look into the code below to understand the
approach.

Resources to learn digit-dp: [Link]

Time Complexity: min(O(R/C) , O(C)×200×logR)

Space Complexity: O(C)×200×logR

28
Complete Solution: C++

#define int long long

#define ll long long
#define pb push_back
ll a, b, k;
vector < int > v;
int isPrime[300];
const int mod = 1e9 + 7;
void sieve() {
memset(isPrime, 0, sizeof(isPrime));
isPrime[1] = 1;
isPrime[0] = 1;
for (int i = 2; i * i <= 300; i++) {
if (isPrime[i] == 0) {
for (int j = i * i; j < 300; j += i) isPrime[j] = 1;
}
}
}

int dp[12][200][1001][2];
int memo(int index, int sum, int rem, int tight) {
if (index == [Link]()) {
if (isPrime[sum] == 0 && rem == 0) return 1;
return 0;
}
if (dp[index][sum][rem][tight] != -1) return dp[index][sum][rem][tight];
int limit = (tight) ? v[index] : 9;
ll ans = 0;
for (int d = 0; d <= limit; d++) {
int ct = 0;
if (d == v[index]) ct = tight;
ans += memo(index + 1, sum + d, (10 * rem + d) % k, ct);
ans %= mod;
}
return dp[index][sum][rem][tight] = ans;
}

int solveQ(ll n) {
[Link]();
memset(dp, -1, sizeof(dp));
while (n) {
[Link](n % 10);
n = n / 10;
}
reverse([Link](), [Link]());
return memo(0, 0, 0, 1);
}

bool check(ll n) {
int sum = 0;
while (n) {
sum += n % 10;
n = n / 10;
}
if (isPrime[sum] == 0) return true;
return false;
}

29
int32_t Solution::solve(string A, string B, int32_t C) {
sieve();
a = 0;
b = 0;
for (int c: A) {
a = (a * 10) + (c - '0');
}

for (int c: B)
b = (b * 10) + (c - '0');
k = (long) C;
if (k <= 1000)
return solveQ(b) - solveQ(a - 1);
else {
ll res = 0;
ll start = (a / k) * k;
if (start < a) start += k;
for (ll i = start; i <= b; i += k) {
if (check(i)) res++;
}
return res;
}
return 0;
}

30
Complete Solution: Java

public class Solution {

static boolean[] p;
static long mod = 1000000007;
static void seive(boolean p[]) {

p[0] = true;
p[1] = true;
for (int i = 2; i * i < [Link]; i++)
if (p[i] == false) {
for (int j = i * i; j < [Link]; j = j + i)
p[j] = true;
}
}

static long[][][][] dp;

static long calc(char s[], int pos, int sum, int rem, int flag, int k) {

if (pos == [Link])
return (p[sum] == false && rem == 0) ? 1 : 0;
if (dp[pos][sum][rem][flag] != -1)
return dp[pos][sum][rem][flag];

long ans = 0;

int maxd = flag == 1 ? 9 : (s[pos] - '0');

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

int zz = (flag == 1 || i < maxd) ? 1 : 0;
ans = ans + calc(s, pos + 1, sum + i, (rem * 10 + i) % k, zz, k);
ans %= mod;
}
return dp[pos][sum][rem][flag] = ans;
}

static long solve1(long n, int k1) {

char s[] = (n + "").toCharArray();
dp = new long[[Link]][200][k1][2];
for (int i = 0; i < [Link]; i++)
for (int j = 0; j < 200; j++)
for (int k = 0; k < k1; k++)
for (int l = 0; l < 2; l++)
dp[i][j][k][l] = -1;

return calc(s, 0, 0, 0, 0, k1);

}

static boolean check(long num) {

int s = 0;
while (num > 0) {
s = s + (int)(num % 10);
num = num / 10;
}
return p[s] == false ? true : false;
}

31
 public int solve(String a, String b, int C) {
p = new boolean[200];
seive(p);
long A = 0;
long B = 0;
long k = (long) C;

for (int i = 0; i < [Link](); i++)

A = (A * 10) + ([Link](i) - '0');

for (int i = 0; i < [Link](); i++)

B = (B * 10) + ([Link](i) - '0');

long ans = 0;

if (k <= 1500)
ans = solve1(B, (int) k) - solve1(A - 1, (int) k);
else {
long st = 0;

if (A % k == 0)
st = A;
else
st = (A / k + 1) * k;

for (long j = st; j <= B; j = j + k)

if (check(j)) {
ans++;
ans %= mod;
}
}
return (int) ans;
}
}

32
Additional Problems 1 – Palindromic Beauty
Hint:

The basic idea is while traversing through the numbers we can keep another pointer J
(where J initially points to the last digit of the number).

This pointer will gradually decrease.

We will simply try to put the digit (that we are currently generating in our recursive
function) at the Jth position of the number.

This will ensure the number is a palindrome.

Solution Approach:

Now back to my approach, the basic idea is while traversing through the numbers, we
can keep another pointer J (where J initially points to the last digit of the number).

This pointer will gradually decrease. We will simply try to put the digit (that we are
currently generating in our recursive function) at the Jth position of the number. This
will ensure the number is a palindrome.

Now the tricky part is how to validate the generated number at the base case? For this,
we need to keep another flag in our state. This flag will be very similar to the Basic Digit
DP flag and will be kept for the J pointer. This flag will tell us if we have set any illegal
digit using J pointer. In my code, I have used this flag to determine whether the number
that I have generated till current J pointer, is bigger than the actual number until the
current J pointer or not.

In the base case, by combining both the flags’ status we can easily determine whether
the current generated number is larger than the actual number or not.

I also used another flag, which tells if the first digit of the number is non-zero. This was
used to prevent the J pointer from putting illegal 0 at the end of the number (when the
actual number generation has not yet started to generate).

Time Complexity: O(A[i])

Space Complexity: O(A[i])

33
Complete Solution: C++

#include<bits/stdc++.h>
#define ll long long
#define M 1000000007
#define rep(i, a, b) for (ll i = (ll) a; i < (ll) b; i++)
#define sz(a)(ll) [Link]()
string s;
ll p[17], dp[20][2][2];
ll f(ll i, ll t, ll fl) {
if (i == (sz(s) + 1) / 2)
return ((t & fl) ^ 1);
if (dp[i][t][fl] != -1)
return dp[i][t][fl];
ll lim = (t ? s[i] - '0' : 9);
ll ans = 0;
rep(j, int(i == 0), lim + 1) {
int nfl = fl;
if (j < s[sz(s) - 1 - i] - '0')
nfl = 0;
else if (j > s[sz(s) - 1 - i] - '0')
nfl = 1;
ans += f(i + 1, t & (j == lim), nfl);
}
dp[i][t][fl] = ans;
return ans;
}
ll g(ll num) {
if (num < 0)
return 0;
s = to_string(num);
ll ans = 1;
rep(i, 1, sz(s))
ans += 9 * p[(i + 1) / 2 - 1];
memset(dp, -1, sizeof(dp));
ans += f(0, 1, 0);
return ans;
}
vector < int > Solution::solve(vector < string > & A) {
p[0] = 1;
rep(i, 1, 16)
p[i] = 10 * p[i - 1];
vector < int > ans;
for (int i = 0; i < [Link](); i += 2) {
ll l = stoll(A[i]), r = stoll(A[i + 1]);
ans.push_back((g(r) - g(l - 1)) % M);
}
return ans;
}

34
Complete Solution: Python

le = 0
digitUp = [0 for i in range(20)]

def toDigUpper(x):
stk = []
while x:
[Link](x % 10)
x //= 10
if len(stk) == 0:
[Link](0)
global le
while len(stk):
digitUp[le] = [Link]()
le += 1

dp = [
[
[[[-1 for i5 in range(2)] for i4 in range(2)] for i3 in range(2)]
for i2 in range(17)
]
for i1 in range(17)
]

def rec(pos, noLimitOfPrvPos, start, backPos, greater):

if pos > backPos:
if not noLimitOfPrvPos and greater:
return 0
return 1
if dp[pos][backPos][noLimitOfPrvPos][start][greater] != -1:
return dp[pos][backPos][noLimitOfPrvPos][start][greater]

limit = 0
if noLimitOfPrvPos == True:
limit = 9
else:
limit = digitUp[pos]

ret = 0
for i in range(0, limit + 1):
if start == 0 and i == 0:
ret += rec(
pos + 1, noLimitOfPrvPos or i < digitUp[pos], 0, backPos,
greater
)
elif pos == backPos:
ret += rec(
pos + 1,
noLimitOfPrvPos or i < digitUp[pos],
start | i > 0,
backPos,
greater,
)
else:

35
 if i == digitUp[backPos]:
ret += rec(
pos + 1,
noLimitOfPrvPos or i < digitUp[pos],
start | i > 0,
backPos - 1,
greater,
)
continue

ret += rec(
pos + 1,
noLimitOfPrvPos or i < digitUp[pos],
start | i > 0,
backPos - 1,
i > digitUp[backPos],
)
dp[pos][backPos][noLimitOfPrvPos][start][greater] = ret
return ret

def getAns(x):
if x < 0:
return 0
if x < 10:
return x + 1
global le, dp
dp = [
[
[[[-1 for i5 in range(2)] for i4 in range(2)] for i3 in
range(2)]
for i2 in range(17)
]
for i1 in range(17)
]
le = 0
toDigUpper(x)
return rec(0, False, 0, le - 1, False)

class Solution:
# @param A : list of strings
# @return a list of integers
def solve(self, A):
ans = []
for i in range(0, len(A), 2):
[Link]((getAns(int(A[i + 1])) - getAns(int(A[i]) - 1)) %
1000000007)
return ans

36
Complete Solution: Java

public class Solution {

final int mod = (int) 1e9 + 7;
String s;
long[][][] dp = new long[20][2][2];

long rec(int idx, int greater, int tight) {

if (idx == ([Link]() + 1) / 2) {
if (tight == 1 && greater == 1) {
return 0;
}
return 1;
}
if (dp[idx][greater][tight] != -1) {
return dp[idx][greater][tight];
}
long ans = 0;
int lim = (tight == 1) ? (int)([Link](idx) - '0') : 9;
for (int i = 0; i <= lim; i++) {
if (i == 0 && idx == 0) {
continue;
}
int new_greater = greater;
if (tight == 1 && i == lim) {
if ([Link](idx) < [Link]([Link]() - 1 - idx)) {
new_greater = 0;
} else if ([Link](idx) > [Link]([Link]() - 1 - idx)) {
new_greater = 1;
}
ans = (ans + rec(idx + 1, new_greater, 1)) % mod;
} else {
ans = (ans + rec(idx + 1, new_greater, 0)) % mod;
}
}
return dp[idx][greater][tight] = ans;
}

long helper(String A) {
s = A;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
dp[i][j][k] = -1;
}
}
}

long ans = 0, temp;

for (int i = 1; i <= [Link]() - 1; i++) {
temp = 9;
for (int j = 1; j <= (i - 1) / 2; j++) {
temp = (temp * 10) % mod;
}
ans = (ans + temp) % mod;
}
ans = (ans + rec(0, 0, 1)) % mod;
return ans;
}

37
 public int[] solve(String[] A) {
int[] ans = new int[[Link] / 2];
for (int i = 0; i < [Link]; i += 2) {
long l, r, left, right = 0;
l = [Link](A[i]);
r = [Link](A[i + 1]);
left = helper([Link](l - 1));
right = helper([Link](r));
ans[i / 2] = (int)(right - left + mod) % mod;
}
return ans;
}
}

38
Additional Problems 2 – Double Sum
Hint:

We can convert the query from a to b to two queries from 0 to b and 0 to a - 1.

How can we do it from [0, n]?

Let’s say we keep a digit at a position?

How can we keep track that the number is less than n?

Solution Approach:
Straight forward Digit Dp problem, where we need to find the
sum of digits in the range [A, B].
To find sum in range [A, B], we can do so by sum([0,B]) -
sum([0,A))
We use Digit DP to solve the above problem.

The states of DP index, tight, started and sum.

// DP[idx][tight][started][sum]

1) index states the current index we are at

2) tight = 1, denotes that the current number being formed

is tight
3) started denotes if we have started taking digits in our
recursion
4) sum tells the sum of the digit so far

Time Complexity: O(|A| * (|A[i]| * 2 * 2 * 200 ) )

Space Complexity: O(|A[i]| * 2 * 200)

39
Complete Solution: C++
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

const ll MOD = 1e9 + 7;
vector <int> num;

// DP[idx][tight][started][sum]
ll dp[20][2][2][200];

ll rec(int idx, int tight, int started, int sum) {

// If we traversed the whole num array
if( idx == [Link]() ) return sum;
// upper bound, possible digits that can be taken for current index
int ub = tight ? num[idx]: 9;
ll &ans = dp[idx][tight][started][sum];
// if answer is already calculated
if( ~ans ) return ans; ans = 0;
if( !started ) { // If we have not yet started taking the number
// Skipping current index
ans = rec(idx + 1, 0, 0, 0);
for( int i = 1; i <= ub; i += 1) {
// starting with the first digit as i and updating tight
accordingly
ans += rec(idx+1, tight&(ub==i),1,sum + i);
ans = (ans + MOD) % MOD;
}
} else { // already started the number
for( int i = 0; i <= ub; i += 1) {
// taking ith digit for the current index and updating tight
accordingly
ans += rec(idx+1, tight&(i==ub),1,sum + i);
ans = (ans + MOD) % MOD;
}
}
return ans;
}
ll solve1(ll x) {
[Link]();
// create a num vector that stores the digit of the number in an array
format
while (x) {
num.push_back(x % 10);
x /= 10;
}
reverse([Link](), [Link]());
// initilize the DP with -1
memset(dp, -1, sizeof(dp));
// call the rec function to get the sum of digits in range [0,x]
return rec(0, 1, 0, 0);
}
vector<int> Solution::solve(vector < string > & A) {
vector<int> ans;
for (int i = 0; i < [Link](); i += 2)
// ans = sum(R) - sum(L-1)
ans.push_back((solve1(stoll(A[i + 1])) - solve1(stoll(A[i]) - 1) +
MOD) % MOD);
return ans;
}

40
Complete Solution: Python

num = []
mod = 1000000007
dp = {}

def call(pos, flag, total):

global dp, mod, num
if pos == len(num):
return total
state = (pos, flag, total)
if state in dp:
return dp[state]
lim = num[pos]
if flag:
lim = 9
ans = 0
for i in range(lim + 1):
new_flag = flag
if i < num[pos]:
new_flag = 1
ans += call(pos + 1, new_flag, total + i)
ans %= mod
dp[state] = ans
return ans

def f(x):
global num, dp
num = []
while x > 0:
[Link](x % 10)
x //= 10
num = num[::-1]
dp = {}
return call(0, 0, 0)

class Solution:
# @param A : list of strings
# @return a list of integers
def solve(self, A):
global mod
q = len(A) // 2
ret = []
for i in range(q):
[Link]((f(int(A[2 * i + 1])) - f(int(A[2 * i]) - 1) + mod)
% mod)
return ret

41
Complete Solution: Java

import [Link];
import [Link];
public class Solution {
final long MOD = (int) 1e9 + 7;
long[][][] dp = new long[20][2][300];
Vector < Integer > num = new Vector < > ();

public long call(int pos, int f1, int sum) {

if (pos == [Link]()) {
return sum;
}

long ret = dp[pos][f1][sum];

if (ret != -1) return ret;

int LIM = (f1 > 0) ? 9 : [Link](pos);

long ans = 0;

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

ans = (ans + call(pos + 1, i < [Link](pos) ? 1 : f1, sum + i)) %
MOD;
}
dp[pos][f1][sum] = ans;
return ans;
}

public long helper(long x) {

[Link]();
while (x > 0) {
[Link]((int)(x % 10));
x /= 10;
}
[Link](num);
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 300; k++) {
dp[i][j][k] = -1;
}
}
}

return call(0, 0, 0);

}
public int[] solve(String[] A) {
int[] ans = new int[[Link] / 2];
for (int i = 0; i < [Link]; i += 2) {
long l, r, diff, left = 0, right;
l = [Link](A[i]) - 1;
r = [Link](A[i + 1]);
left = helper(l);
right = helper(r);
diff = (right - left + MOD) % MOD;
ans[i / 2] = (int) diff;
}
return ans;
}
}

42
Additional Problems 3 – Jesse and Maths
Hint:

Try to use digit dp to solve this problem.

Try to think of four states in digit dp table to solve this problem?

Solution Approach:

DP[i][j][k][t] denotes number of pairs, with above condition such that i most significant
digits from left have been seen, difference between digit sums of first and second
number is j,

k = 0 denotes that the second number already has become smaller than N after
considering most significant i digits,
k = 1 denotes that the second number is equal to N, if most significant i digits are
considered,
t = 0 denotes that first number has become smaller than second after comparing i most
significant digits and
t = 1 denotes that first and second number are still equal if only i most significant digits
are considered.

For every state, we iterate over all the 10 * 10 digit combinations.

Time Complexity: O( 1000 * log10(N) * log10(N) )

43
Complete Solution: C++

#define ll long long

const int N = 260;
const int base = 10 * N;
const int mod = 1e9 + 7;
ll dp[N][N * 20][2][2]; //[index][sum_diff][less?][tight?]

ll helper(int idx, int diff, int less, int tight, string & s) {
// When whole string is traversed
if (idx == [Link]()) {
// difference should be greater than 0 and it should be less
if (diff > base && less == 1) return 1;
return 0;
}
// If the DP state is already claculated
if (dp[idx][diff][less][tight] != -1) return dp[idx][diff][less]
[tight];
ll ans = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
int new_diff = diff + j - i;
int new_less = less;
int new_tight = tight;
// update the less, less = 1, if i < j
if (less == 0) {
if (i < j) {
new_less = 1;
} else if (i > j) {
continue;
}
}
// Update the tight
if (tight == 1) {
if (j < s[idx] - '0') {
new_tight = 0;
} else if (j > s[idx] - '0') {
continue;
}
}
// Call the helper again for further states
ans = (ans + helper(idx + 1, new_diff, new_less, new_tight,
s)) % mod;
}
}
return dp[idx][diff][less][tight] = ans;
}

int Solution::solve(string A) {
memset(dp, -1, sizeof dp);
// base is passed as the difference of digit can become negative
ll ans = helper(0, 0 + base, 0, 1, A);
return (int) ans;
}

44
Complete Solution: Python

import sys

def countPairs(N):
N = list(reversed([int(d) for d in str(N)]))
digits_N = len(N)

MODBASE = 10 ** 9 + 7

D = [[0] * (digits * 9 + 1) for digits in range(251)]

D[0][0] = 1

for digits in range(1, 251):

for sum_digits in range((digits - 1) * 9 + 1):
D[digits][sum_digits] = D[digits - 1][sum_digits]

for first_digit in range(1, 10):

for sum_digits in range(first_digit, first_digit + (digits -
1) * 9 + 1):
D[digits][sum_digits] += D[digits - 1][sum_digits -
first_digit]
D[digits][sum_digits] %= MODBASE

# cumD[d][s] = number of d-digit nunmber (with potential leading

zeros) with digit-sum <= s
cumD = [[0] * (digits * 9 + 1) for digits in range(251)]
for digits in range(251):
cumD[digits][0] = D[digits][0]
for s in range(1, len(D[digits])):
cumD[digits][s] = cumD[digits][s - 1] + D[digits][s]
cumD[digits][s] %= MODBASE

Q = [0] * 251
for digits in range(1, 251):
Q[digits] = (10 * Q[digits - 1]) % MODBASE
count = [0] * 10

for diff in range(1, 10):

for sy in range((digits - 1) * 9 + 1):
sxmax = min(sy + diff - 1, (digits - 1) * 9)
Q[digits] += (10 - diff) * D[digits - 1][sy] * cumD[digits
- 1][sxmax]

# A[d][s] = number of d-digit numbers less than N[1..d] having sum of

digits s
A = [[0] * ((digits + 1) * 9 + 1) for digits in range(digits_N + 1)]

for d in range(digits_N):
D[d][0] = 1
for first_digit in range(N[d]):
for sum_digits in range(9 * (d) + 1):
A[d][sum_digits + first_digit] += D[d][sum_digits]

for sum_digits in range(9 * (d) + 1):

A[d][sum_digits + N[d]] += A[d - 1][sum_digits] if d > 0 else
1

45
 # P[d] = number of pairs x, y such that only the d least significant
digits are different from N
P = [0] * digits_N
P[0] = N[0] * (N[0] + 1) // 2

for d in range(1, digits_N):

a1 = N[d]

# x1=y1=a1
P[d] = P[d - 1] + a1 * Q[d]

for diff in range(1, a1):

for sy in range((d) * 9 + 1):
sxmax = min(sy + diff - 1, (d) * 9)
P[d] += (a1 - diff) * D[d][sy] * cumD[d][sxmax]

for x1 in range(a1):
y1 = a1
for sy in range(d * 9 + 1):
sxmax = min(sy + y1 - x1 - 1, d * 9)
P[d] += A[d - 1][sy] * cumD[d][sxmax]

return P[digits_N - 1] % MODBASE

class Solution:
# @param A : string
# @return an integer
def solve(self, A):
result = countPairs(A)
return result

46
Complete Solution: Java

public class Solution {

static long mod = 1000000007;
static String s;
static int N = 260;

static int[][][][] dp = new int[N][N * 10 * 2][2][2];

static int base = 10 * N;

public int solve(String A) {

for (int i = 0; i < N; i++) {
for (int j = 0; j < N * 10 * 2; j++) {
for (int k = 0; k < 2; k++) {
dp[i][j][k][0] = -1;
dp[i][j][k][1] = -1;
}
}
}

s = A;
long ans = solve(0, 0 + base, 0, 0);

return (int) ans;

}

public static long solve(int idx, int dif, int fs, int sn) {

if (fs == 2 || sn == 2)
return 0;

if (dp[idx][dif][fs][sn] != -1)
return dp[idx][dif][fs][sn];

if (idx == [Link]()) {
if (fs == 1 && dif - base > 0)
return 1;

return 0;
}

long ans = 0;

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

for (int j = 0; j < 10; j++) {

int ndif = dif + j - i;

int nfs = fs;

if (fs == 0) {
if (i < j)
nfs = 1;
else if (i == j)
nfs = 0;
else
continue;
}

47
 int nsn = sn;

if (sn == 0) {
if (j < [Link](idx) - '0')
nsn = 1;
else if (j == [Link](idx) - '0')
nsn = 0;
else
continue;
}

ans = ans + solve(idx + 1, ndif, nfs, nsn);

}

if (ans >= mod)

ans = ans % mod;

return dp[idx][dif][fs][sn] = (int) ans;

}
}

48
Assignment Question 1 – Find Magic Numbers – Solution

public class Solution {

static final int MOD = (int) 1e9 + 7;

static int memo[][][][];

static int pow[];
static int m, d;

static char[] digits;

static char[] digits1;

static int dp(int pos, int less, int greater, int div) {
if (pos == [Link])
return div == 0 ? 1 : 0;

if (memo[less][greater][pos][div] != -1)
return memo[less][greater][pos][div];

long ans = 0;
int LIMIT = (less == 1 ? 9 : digits[pos] - '0'), start = (greater == 1 ? 0
: digits1[pos] - '0');

for (int i = start; i <= LIMIT; i++)

if ((pos % 2 == 0 && i != d) || (pos % 2 == 1 && i == d))
ans = (long) add((int) ans, dp(pos + 1, less | (i < LIMIT ? 1 : 0),
greater | (start < i ? 1 : 0), add(div, mult(i, pow[pos], m), m)), MOD);

return memo[less][greater][pos][div] = (int) ans;

}

static int mult(int x, int y, int MOD) {

return (int)((1l * x * y) % MOD);
}

static int add(int x, int y, int MOD) {

int ans = x + y;

return ans % MOD;

}

static int modPow(int a, int e, int MOD) {

int res = 1;

while (e > 0) {
if ((e & 1) == 1)
res = mult(res, a, MOD);

a = mult(a, a, MOD);

e >>= 1;
}

return res;
}

49
 static void init() {
for (int[][][] x: memo)
for (int[][] xx: x)
for (int[] xxx: xx)
[Link](xxx, -1);

public int solve(String A, String B, int C, int D) {

m = C;
d = D;

String a = A;
String b = B;

memo = new int[2][2][[Link]()][m];

pow = new int[[Link]()];

for (int i = 0; i < [Link]; i++)

pow[i] = modPow(10, [Link] - i - 1, m);

init();

digits = [Link]();
digits1 = [Link]();

return (dp(0, 0, 0, 0));

}
}

50
Assignment Question 2 – Non Zero Digits – Solution

public class Solution {

final long mod = (int) 1e9 + 7;

long[][][] dp = new long[20][3][2];

public long solve(int idx, int non_zero, int tight, String s) {

if (idx == [Link]()) {
return 1;
}

if (non_zero == 3) {
return 1;
}

if (dp[idx][non_zero][tight] != -1) {
return dp[idx][non_zero][tight];
}

if (tight == 0) {
dp[idx][non_zero][tight] = (9 * solve(idx + 1, non_zero + 1, tight, s)
+ solve(idx + 1, non_zero, tight, s)) % mod;
} else {
int dig = (int)([Link](idx) - '0');

if (dig == 0) {
dp[idx][non_zero][tight] = solve(idx + 1, non_zero, tight, s);
} else {
dp[idx][non_zero][tight] = (solve(idx + 1, non_zero, (tight ^ 1),
s) + (dig - 1) * solve(idx + 1, non_zero + 1, (tight ^ 1), s) + solve(idx + 1,
non_zero + 1, tight, s)) % mod;
}
}

return dp[idx][non_zero][tight];
}

public long helper(String s) {

for (int i = 0; i < 20; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 2; k++) {
dp[i][j][k] = -1;
}
}
}

return solve(0, 0, 1, s);

}

51
 public int[] solve(String[] A) {
int[] ans = new int[[Link] / 2];

for (int i = 0; i < [Link]; i += 2) {

long l, r, left, right, diff = 0;

l = [Link](A[i]);
r = [Link](A[i + 1]);

left = helper([Link](l - 1));

right = helper([Link](r));

diff = (right - left + mod) % mod;

ans[i / 2] = (int) diff;

}

return ans;
}
}

52
Assignment Question 3 – Playing among Digits – Solution

public class Solution {

static boolean[] p;

static long mod = 1000000007;

static void seive(boolean p[]) {

p[0] = true;
p[1] = true;

for (int i = 2; i * i < [Link]; i++) {

if (p[i] == false) {
for (int j = i * i; j < [Link]; j = j + i)
p[j] = true;
}
}
}

static long[][][][] dp;

static long calc(char s[], int pos, int sum, int rem, int flag, int k) {
if (pos == [Link])
return (p[sum] == false && rem == 0) ? 1 : 0;

if (dp[pos][sum][rem][flag] != -1)
return dp[pos][sum][rem][flag];

long ans = 0;
int maxd = flag == 1 ? 9 : (s[pos] - '0');

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

int zz = (flag == 1 || i < maxd) ? 1 : 0;

ans = ans + calc(s, pos + 1, sum + i, (rem * 10 + i) % k, zz, k);

ans %= mod;
}

return dp[pos][sum][rem][flag] = ans;

}

static long solve1(long n, int k1) {

char s[] = (n + "").toCharArray();

dp = new long[[Link]][200][k1][2];

for (int i = 0; i < [Link]; i++)

for (int j = 0; j < 200; j++)
for (int k = 0; k < k1; k++)
for (int l = 0; l < 2; l++)
dp[i][j][k][l] = -1;

return calc(s, 0, 0, 0, 0, k1);

}

53
 static boolean check(long num) {
int s = 0;

while (num > 0) {

s = s + (int)(num % 10);
num = num / 10;
}

return p[s] == false ? true : false;

}

public int solve(String A, String B, int C) {

p = new boolean[200];

seive(p);

long a = 0;
long b = 0;
long k = (long) C;

for (int i = 0; i < [Link](); i++)

a = (a * 10) + ([Link](i) - '0');

for (int i = 0; i < [Link](); i++)

b = (b * 10) + ([Link](i) - '0');

long ans = 0;

if (k <= 1500)
ans = solve1(b, (int) k) - solve1(a - 1, (int) k);
else {
long st = 0;

if (a % k == 0)
st = a;
else
st = (a / k + 1) * k;

for (long j = st; j <= b; j = j + k)

if (check(j)) {
ans++;

ans %= mod;
}
}

return (int) ans;

}
}

54
Additional Problems 1 – Palindromic Beauty – Solution

public class Solution {

final int mod = (int) 1e9 + 7;
String s;
long[][][] dp = new long[20][2][2];

long rec(int idx, int greater, int tight) {

if (idx == ([Link]() + 1) / 2) {
if (tight == 1 && greater == 1) {
return 0;
}
return 1;
}

if (dp[idx][greater][tight] != -1) {
return dp[idx][greater][tight];
}

long ans = 0;
int lim = (tight == 1) ? (int)([Link](idx) - '0') : 9;

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

if (i == 0 && idx == 0) {
continue;
}

int new_greater = greater;

if (tight == 1 && i == lim) {

if ([Link](idx) < [Link]([Link]() - 1 - idx)) {
new_greater = 0;
} else if ([Link](idx) > [Link]([Link]() - 1 - idx)) {
new_greater = 1;
}

ans = (ans + rec(idx + 1, new_greater, 1)) % mod;

} else {
ans = (ans + rec(idx + 1, new_greater, 0)) % mod;
}
}

return dp[idx][greater][tight] = ans;

}

long helper(String A) {
s = A;

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

for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
dp[i][j][k] = -1;
}
}
}

55
 long ans = 0, temp;

for (int i = 1; i <= [Link]() - 1; i++) {

temp = 9;

for (int j = 1; j <= (i - 1) / 2; j++) {

temp = (temp * 10) % mod;
}

ans = (ans + temp) % mod;

}

ans = (ans + rec(0, 0, 1)) % mod;

return ans;
}

public int[] solve(String[] A) {

int[] ans = new int[[Link] / 2];

for (int i = 0; i < [Link]; i += 2) {

long l, r, left, right = 0;

l = [Link](A[i]);
r = [Link](A[i + 1]);

left = helper([Link](l - 1));

right = helper([Link](r));

ans[i / 2] = (int)(right - left + mod) % mod;

}

return ans;
}
}

56
Additional Problems 2 – Double Sum – Solution

import [Link];
import [Link];

public class Solution {

final long MOD = (int) 1e9 + 7;

long[][][] dp = new long[20][2][300];

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

public long call(int pos, int f1, int sum) {

if (pos == [Link]()) {
return sum;
}

long ret = dp[pos][f1][sum];

if (ret != -1) return ret;

int LIM = (f1 > 0) ? 9 : [Link](pos);

long ans = 0;

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

ans = (ans + call(pos + 1, i < [Link](pos) ? 1 : f1, sum + i)) % MOD;
}

dp[pos][f1][sum] = ans;

return ans;
}

public long helper(long x) {

[Link]();

while (x > 0) {
[Link]((int)(x % 10));
x /= 10;
}

[Link](num);

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

for (int j = 0; j < 2; j++) {
for (int k = 0; k < 300; k++) {
dp[i][j][k] = -1;
}
}
}

return call(0, 0, 0);

}

57
 public int[] solve(String[] A) {
int[] ans = new int[[Link] / 2];

for (int i = 0; i < [Link]; i += 2) {

long l, r, diff, left = 0, right;

l = [Link](A[i]) - 1;
r = [Link](A[i + 1]);

left = helper(l);
right = helper(r);

diff = (right - left + MOD) % MOD;

ans[i / 2] = (int) diff;

}

return ans;
}
}

58
Additional Problems 3 – Jesse and Maths – Solution

public class Solution {

static long mod = 1000000007;
static String s;
static int N = 260;
static int[][][][] dp = new int[N][N * 10 * 2][2][2];
static int base = 10 * N;

public int solve(String A) {

for (int i = 0; i < N; i++) {
for (int j = 0; j < N * 10 * 2; j++) {
for (int k = 0; k < 2; k++) {
dp[i][j][k][0] = -1;
dp[i][j][k][1] = -1;
}
}
}

s = A;
long ans = solve(0, 0 + base, 0, 0);

return (int) ans;

}

public static long solve(int idx, int dif, int fs, int sn) {
if (fs == 2 || sn == 2)
return 0;

if (dp[idx][dif][fs][sn] != -1)
return dp[idx][dif][fs][sn];

if (idx == [Link]()) {
if (fs == 1 && dif - base > 0)
return 1;

return 0;
}

long ans = 0;

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

for (int j = 0; j < 10; j++) {
int ndif = dif + j - i;
int nfs = fs;

if (fs == 0) {
if (i < j)
nfs = 1;
else if (i == j)
nfs = 0;
else
continue;
}

59
 int nsn = sn;

if (sn == 0) {
if (j < [Link](idx) - '0')
nsn = 1;
else if (j == [Link](idx) - '0')
nsn = 0;
else
continue;
}

ans = ans + solve(idx + 1, ndif, nfs, nsn);

}

if (ans >= mod)

ans = ans % mod;
}

return dp[idx][dif][fs][sn] = (int) ans;

}
}

60