9 weeks ago

John 910

Hyderabad

Question 1

You are given four values L, R, X, and Y. Count the number of integers in the range [L,R] with the following property:

The number of digits with Odd Frequency = X and the number of digits with Even Frequency = Y.

Also (X+Y=10)

Here, the Frequency of a digit is a count of the number of times it occurs in the decimal representation of the numbers (without a leading zeros).

Note: If a digit 'd' occurs in a number 0 times, then it is considered to have an even frequency.

The answer could be an large; find it modulo (10^9 + 7).

Input Format

The first line will contain four values L, R, X and Y.

Output Format

The number of integers in [L,R] with given property modulo (10^9 + 7).

Sample Testcase

Testcase Input
1    1000    0   10


Testcase Output
9

Question 2

There are 2 boys in a class who have been given a target, k by their class teacher.

These students have several lists of blocks having numbered from them. They are to find a block such that the largest and smallest of the remaining blocks have a difference at most as the target.

Help them find the desired box to be removed.

Constraints

• 1 <= n <= 100000
• 1 <= arr[i] <= 100000

Input Format

• The first line contains an integer n and an integer k.
• The second line contains n space-separated integers representing the array.

Output Format

• Print m - the minimum number which we have to remove the array to satisfy the condition

Sample Testcase

Testcase Input
3    3
5    10     2

Testcase Output
1

8 months ago

Shikhar Mehrotra 480

Chennai

Q1) Assuming length of both L and R could be atmost 1000
It can be solved using digit dp:
Let f(int idx,bool tight,bool lead,int mask,string R) represent count of integers <=R such that we have kept numbers at position [0,idx-1] and

1.if tight=1 it means that currently number formed [0,idx-1] and R[0,idx-1] are equal
2.if tight=0 it means that currently number formed [0,idx-1] is less than R[0,idx-1]
3.if lead =1 it means that there are leading zeros currently.

1. mask is 10 bit integer , if mask's dth bit is 1 then it means digit d had odd frequency in the currently formed number and if it is 0 it means digit d has even frequency in currently formed number.

Hence we can define the recursion by ub is maximum allowed digit on the idx position if tight=1 ; ub=R[idx]-'0' ; tight=0 ; ub=9:

for(d in [0,...,ub])
{
    if(!lead)
    {
        ans+=f(idx+1,(tight && (d==ub)),lead,(mask^(1 < < d)),s,n);
    }
    else
    {
        if(d==0)
        {
            ans+=f(idx+1,(tight&&(d==ub)),1,mask,s,n);
        }
        else
        {
            ans+=f(idx+1,(tight&&(d==ub)),0,(mask^(1 < < d)),s,n);
        }
    }
    ans%=mod;
}

and the base case could be

if(idx==length(R))
 {
 if(count of setbits in mask is X and count of zerobits in mask is Y)
   return 1
 return 0
  }

Hence the answer is f(0,1,1,0,R)-f(0,1,1,0,L-1)
We could improve the complexity by memoizing the states {idx,tight,lead,mask}

2.1 years ago

Sumeet Kumar Mishra • 10

Q2) The problem can be solved using binary search over the number of elements that are to be removed. We need to find the minimum z, such that by removing some z elements of the array we can satisfy our constraint (difference of maximum and minimum is less than or equal to k). The following set of observations help us formulate the problem

1. It is always beneficial to remove either the minimum or maximum of the remaining elements in the array. Hence, let us first sort the array
2. Due to this the elements to be removed would be a prefix of the array combined with a suffix of the array
3. The difference of the maximum and the minimum is a decreasing function of the number of elements removed (call this n_removed)

Pseudo code

def check_valid(arr,  n,  k,  n_removed):
    for i in range(n_removed + 1):
        if arr[n - 1 - n_removed + i] - arr[i] <= k:
            return True
    return False

def solve(arr, n, k):
    hi = n - 1
    lo = 0
    while lo < hi:
        mid = (lo + hi) // 2
        if check_valid(arr, n, k, mid):
            hi = mid
        else:
            lo = mid + 1

    return lo