1 day ago

John 500

Question 1

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.

Question 2

Odd Even Prime Multiples

3 months ago

Gurankit Pal Singh 140

Solution to problem 1

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.

1. index signifies the current index of the number being formed.
2. remainder signifies the remainder of the number formed so far.
3. tight would take value 0 or 1, representing if the prefix of the number formed is equal to prefix of x.
4. 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.

Pseudo Code:

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
    }