Entering edit mode

Click here to Practice

Submit Problem to OJ

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:**

- 1 <= p <= 25
- 1 <= L,R< 10^99

**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.

Entering edit mode

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*.

*index*signifies the current index of the number being formed.*remainder*signifies the remainder of the number formed so far.*tight*would take value 0 or 1, representing if the prefix of the number formed is equal to prefix of*x*.*startStatus*will take values 0,1 or 2. 0 represents that all the previous digits of the number are 0 (it would be helpful when the length of the final number formed is less than the length of x). 1 represents that all the previous digits of the number are 0, and we will start forming the number at the current index. 2 represents that the number has already some non zero digits in it.

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
}
```

Loading Similar Posts

Bro can u send the complete code