Question: CITI Bank, Previously Asked Coding Questions, 2022 | Ways To Make Coin Change | Non-Decreasing Array

Entering edit mode

Avg CTC: 18lpa

Job Roles: Developer, Sr Developer

Location Available: Pune, Bengaluru

Question 1

Ways To Make Coin Change

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

Input Format

The first line of input contains an integer N, representing the total number of denominations. The second line of input contains N integers values separated by a single space. Each integer value represents the denomination value. The third line of input contains the value of V, representing the value for which the change needs to be generated.

Output Format

For each test case, print an integer denoting the total number of ways W, in which a change for V is possible.

Note

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= N <= 10
1 <= D[i] <=10^5
1 <= V <= 2 * 10^3

Where 'D[i]' represent the value of ith denomination.

Time Limit: 1sec

Question 2

Non-Decreasing Array

You have been given an integer array/list 'ARR' of size 'N'. Write a solution to check if it could become non-decreasing by modifying at most 1 element.

We define an array as non-decreasing, if ARR[i] <= ARR[i + 1] holds for every i (0-based) such that (0 <= i <= N - 2).

Input format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains an Integer 'N' denoting the size of the array/list. The second line of each test case contains 'N' space-separated Integers denoting the array/list.

Output format :

For each test case, print a single line containing "true" if it's possible to make 'ARR' non-decreasing array with modifying at most one element or "false" otherwise. The output for every test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 10 ^ 4
-10 ^ 9 <= ARR[i] <= 10 ^ 9

Where 'N' is the size of the given array/list. And, ARR[i] denotes the i-th element in the array/list 'ARR'.

Time Limit: 1sec

ADD COMMENT • link

Entering edit mode

Question 2

Intution

Traverse the array and make the array up to the element covered non-decreasing and count each modification. And we also try to make the last element as small as possible so that in next iterations the possibility of the array to be non-decreasing increases. So we make the elements equal in each non-decreasing sequence found. If modification gets more than 1 then return false else return true.
Now, if we find an element is less than its previous (nums[i] < nums[i-1]) then what are the possibilities?

Either the current element is greater or equal to the previous of previous element (num[i-2] <= nums[i]) In this case, if we make any of the previous (nums[i-1]) of current (nums[i]) equal to one another. But to make the end element as small as possible we make the greater (previous) equal to the smaller (current) i.e. nums[i-1] = nums[i]

      5
     / \
    /    4------                      4 __ 4
   /                                 /
  3-------------     -&gt;             3               Decrease middle element to right one
 /                                 /
2                                 2
 /                                 /
 1                                 1

     5
    / \
   /   \                   
  /     \                           
 3-------3-------     -&gt;           3 __ 3 __ 3        Decrease  middle element to right and left one
 /                                 /
2                                 2
/                                 /
1                                 1

Or the current element is also lesser than the previous of previous element (nums[i-2] > nums[i]).
In this case the array excluding the current element is non-decreasing. But if we exclude the previous element then the last element is still lesser than its previous. So make the current element (smaller) equal to the previous (greater) i.e. nums[i] = nums[i-1]
In case of the second element (nums[1]) if it is lesser than the first (nums[0]) there is no previous of the previous element to compare to so just make both as small as possible so make num[0] = num[1] which is in turn the first condition discussed. So just check if i == 1 in first condition to implement it.
Time Complexity: O(N)

Pseudo Code

 int cnt = 0; //to store the count of modifications                   
    for(int i = 1; i &lt; nums.size(); i++){

        //decreasing sequence found
        if(nums[i] &lt; nums[i-1]){

            //if count after increasing becomes more than 1 then false
            if(++cnt &gt; 1) return false;

            //in case of the 2nd element as i[1] &lt; i[0] so make i[0] = i[1]
            if(i == 1 || nums[i-2] &lt;= nums[i])
                nums[i-1] = nums[i];    
            else 
                nums[i] = nums[i-1];
        }
    }

    return true;

ADD COMMENT • link 2.1 years ago Akshay Sharma 990

Entering edit mode

Question 1

Let dp[i][x] = the number of ways to pick coins with sum x, using the first i coins.

Initially, we say we have dp[0][0] = 1, i.e., we have the empty set with sum zero.

When calculating dp[i][x], we consider the i'th coin. If we didn't pick the coin, then there are dp[i-1][x] possibilities. Otherwise, we picked the coin. Since we are allowed to pick it again, there are dp[i][x — <value of i'th coin>] possibilities.

Hence dp[i][x] = dp[i-1][x] + dp[i][x-D[i]]. Our final answer will be dp[n-1][V].

The complexity is O(N.V)

ADD COMMENT • link 2.1 years ago Nikunj Nawal 10