We are given a integer p and two large numbers in the form of string L and R.
We need to count the no of values between L and R (both inclusive) that are divisible by the p and number should have even value at the odd indices and odd values in the even indices.
Constraints:
Example:
Input:
p=7 L=1 R=25
Output:
2
7,14,21
7- at 0 index(even) we have value 7(odd).
14 - At 0 index we have value 4 which is even, so do not count
21 - 0 index have value 1 and index-1 have value 2.
index 0 starts at the right most position of the value.
Since the range of the numbers are of order 10⁹⁹, checking for each number would give TLE. It can be observed that p is small. This problem can be solved by digit dp. Let the answer for the numbers between 0 to x be f(x), so we will need to calculate f(R)-f(L-1). As L is given in the form of string, to get L-1, we will iterate backward till we don’t find a non zero digit, and decrease it by 1, and all the zeros in the ending would be made 9.
Now coming to the dp transition. Let’s calculate f(x). The states of the dp would be index, remainder, tight, and startStatus.
So, when tight is 1, we cannot place a number greater than the digit at the current index in x. And if we place a smaller digit than the digit at the current index in x, tight will become 0.
If the startStatus is 1, we cannot place 0 at the current index, but if startStatus is 2, we can place 0 at the current index. For each index, we will check if the parity of the index is odd, we will place even digits, else we will place odd digits.
The time and space complexity will be O(n*p)
, where n is the length of the string.
dp[100][25][2][3]
mod = 1e9+7
solve(idx, rem, tight, startstatus, p, x)
if (idx == num.size())
return (rem == 0 && startstatus > 0)
if (dp[idx][rem][tight][startstatus] != -1)
return dp[idx][rem][tight][startstatus]
if (startstatus > 0) {
ans = 0, i = 1
if((num.size() % 2) == (idx % 2))
i = 2
if(startstatus == 2)
i = 0
if(!tight){
for(; i < 10; i += 2)
ans += solve(idx + 1, (rem * 10 + i) % p, tight, 2, p, num)
else
for(; i < num[idx] - '0'; i += 2)
ans += solve(idx + 1,(rem * 10 + i) % p, 0, 2, p, num)
if(i == num[idx] - '0')
ans += solve(idx + 1,(rem * 10 + i) % p, 1, 2, p, num)
return dp[idx][rem][tight][startstatus] = ans;
} else {
option1 = solve(idx, rem, idx == 0 ? 1 : 0, 1, p, num)
option2 = solve(idx + 1, rem, tight, 0, p, num)
return dp[idx][rem][tight][startstatus] = option1 + option2
}
Bro can u send the complete code