Question: Zomato, On-Campus Assessments, October 2022 | Number Formation | Special Keyboard

Entering edit mode

Question 1

Number Formation

Given three integers x, y, and z, the task is to find the sum of all the numbers formed by having 4 at most x times, having 5 at most y times, and having 6 at most z times as a digit.

Note: Output the sum modulo 10^9+7.

Example 1:

Input:

X = 1, Y = 1, Z = 1

Output:

3675

Explanation: 4 + 5 + 6 + 45 + 54 + 56 + 65 + 46 + 64 + 456 + 465 + 546 + 564 + 645 + 654 = 3675

Example 2:

Input:

X = 0, Y = 0, Z = 0

Output:

Explanation: No number can be formed

Constraints:

0 <= X, Y, Z <= 60

Your Task:

You don't need to read input or print anything. Complete the function getSum() which takes X, Y and Z as input parameters and returns the integer value

Expected Time Complexity: O(XYZ)

Expected Auxiliary Space: O(XYZ)

Question 2

Click here to Practice

Special Keyboard

Imagine you have a special keyboard with the following keys:

Key 1: Prints 'A' on screen

Key 2: (Ctrl-A): Select screen

Key 3: (Ctrl-C): Copy selection to buffer

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Find maximum numbers of A's that can be produced by pressing keys on the special keyboard N times.

Example 1:

Input:

N = 3

Output:

Explanation: Press key 1 three times.

Example 2:

Input:

N = 7

Output:

Explanation: The best key sequence is key 1, key 1, key 1, key 2, key 3, key4, key 4.

Constraints:

1 < N < 76

Your Task:

You do not need to read input or print anything. Your task is to complete the function optimalKeys() which takes N as input parameter and returns the maximum number of A's that can be on the screen after performing N operations.

Expected Time Complexity: O(N2)

Expected Auxiliary Space: O(N)

ADD COMMENT • link

Entering edit mode

Question 2

Solution

Given different operations, we have to maximize the number of A's that can be produced.
We basically have 2 ways, either we follow step 1(press key 1) and add a single A or we perform step 2(press key 2) and step 3(press key 3) and then do step 4(press key 4) again and again.

So this basically boils down to a simple dp problem whose code is explained below.

 ll dp[N];
 ll n;
 cin &gt;&gt; n;
 mem0(dp); // initialize with 0
 for (ll i = 1; i &lt;= n; i++)
 {
     dp[i] = 1 + dp[i - 1]; // pressing key 1 takes 1 step and adds 1 A
     for (ll j = 1; j &lt;= i; j++)
     {
         if (i - j &gt;= 3) // If there is scope of selecting,copying  and pasting i.e 3 steps
         {
             dp[i] = max(dp[i], (i - (j + 2) + 1) * dp[j]);//(i-(j+2)) is number of times we can paste and +1 for already pasted stuff.

         }
     }
 }
 cout &lt;&lt; dp[n] &lt;&lt; endl;
 return;

ADD COMMENT • link 2.1 years ago Ujjwal Srivastava 320

Entering edit mode

Question 1

Prerequisite

Sub-Problem overlapping, Dynamic programming and optimal sub-structure strategy.

Approach

The numbers having exact i 4s, j 5s, and k 6s for all i < x, j < y, j < z are required to get the required sum.
Therefore the DP array num[i][j][k] will store the exact count of numbers having exact i 4s, j 5s, and k 6s.
If num[i – 1][j][k], num[i][j – 1][k] and num[i][j][k – 1] are already known, then it can be observed that the sum of these is the required answer, except in the case when num[i – 1][j][k], num[i][j – 1][k] or num[i][j][k – 1] doesn’t exist. In that case, just skip it.

sum[i][j][k] stores the sum of the exact number having i 4’s, j 5’s, and k 6’s.Below is Pseudo Code for that :

         sum[i][j][k] = 10 * (sum[i - 1][j][k] + sum[i][j - 1][k] +sum[i][j][k - 1]) 
            + 4 *num[i - 1][j][k] + 5 *num[i][j - 1][k] + 6 * num[i][j][k - 1]

Time Complexity: O(N^3)

Pseudo Code

 num[0][0][0] = 1;
for (int i = 0; i &lt;= x; ++i)
{
    for (int j = 0; j &lt;= y; ++j)
    {
        for (int k = 0; k &lt;= z; ++k)
        {

            if (i &gt; 0)
            {
                sum[i][j][k] += (sum[i - 1][j][k] * 10 + 4 * num[i - 1][j][k]) % mod;
                num[i][j][k] += num[i - 1][j][k] % mod;
            }
            if (j &gt; 0)
            {
                sum[i][j][k] += (sum[i][j - 1][k] * 10 + 5 * num[i][j - 1][k]) % mod;
                num[i][j][k] += num[i][j - 1][k] % mod;
            }
            if (k &gt; 0)
            {
                sum[i][j][k] += (sum[i][j][k - 1] * 10 + 6 * num[i][j][k - 1]) % mod;
                num[i][j][k] += num[i][j][k - 1] % mod;
            }

            ans += sum[i][j][k] % mod;
            ans %= mod;
        }
    }
}
cout&lt;

ADD COMMENT • link 2.1 years ago Akshay Sharma 990