11 weeks ago

John 910

Hyderabad

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 :Humans have finally made contact with aliens from outer space who call themselves Primes. Naturally, each of their individuals
loves prime numbers. Their emperor loves the prime number p the most. However, their maths is much more advanced than the version we use on Earth. They have very long numbers with several digits going up to 100 digits. A number is said to be valid for them if it follows the following conditions:

• The number must be divisible by the prime number p to keep the emperor happy.

• Even indices must have odd digits, and odd indices must have even digits. Indexing starts from the right end. For example, in the number 123, 3 is at index 0, 2 is at index 1, and 1 is at index 2. Hence if this number is divisible by p,then it can be a valid number.

• The number must not have leading zeroes.

Task

The emperor has sent the message that he will consider humansan intelligent life form if you can tell him the number of valid
numbers between L and R (both inclusive). Since the number of
such numbers can be too large, you only need to tell the answer modulo (10⁹+7).
Assumptions
• p = 7
• 1 = 5
• R = 25
Approach
• One condition of validity is that the number should be
divisible by p (7 in this case). Only the numbers 7, 14, and 21
satisfy this condition in the given range.

You can observe the following from the table:
      • 7 is a valid number as the digit at the even index is odd.
      • 14 is not a valid number as the digit at index O is 4, which is even
       • 21 is a valid number as the digit at index O is odd, and  the digit at index 1 is even.
 Hence, the answer to this case is 2.
Function description
Complete the countPrimeMultiples function provided in the editor. This function takes the following 3 parameters and returns an integer, i.e., the count of such valid numbers in the given range:
• p: Represents the prime number of the emperor
• L: Represents the lower limit of the range of numbers
• R: Represents the upper limit of the range of numbers
Input format
Note: This is the input format you must use to provide custom
input (available above the Compile and Test button).
• The first line contains T denoting the number of test
cases. T also specifies the number of times you have to run
the countPrimeMultiples function on a different set of
inputs.
For each test race

• The first line contains an integer p denoting the primenumber of the emperor. It is guaranteed to be a prime number.
• The Second line contains a string L denoting the lower limit.
• The third line contains a String R denoting the upper limit.

​​​​​Output Format
For each test case in a new line, print a single line containing an
integer modulo (109+7) representing the answer.
Constraints
1 < T < 20
1 ≤ p ≤ 2500
1 ≤ L ≤ R<10⁹⁹

2.1 years ago

Gurankit Pal Singh 160

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
    }