UKG Coding Question – Solved

There is an array of n non-negative integers, arr. In one operation, some positive integer x is chosen and 1 is subtracted from all the numbers of the array which are greater than or equal to x. Find the number of different final arrays possible after the operation is applied 0 or more times. Return the answer modulo (10^9 + 7). Note: 1-based indexing is used. Different values of x can be chosen for different operations. Two final arrays a and b are considered different if there is at least one i (1 ≤ i ≤ n) such that a[i] != b[i]. Example: Consider n = 2, arr = [1, 2]. There are four different final arrays possible. x = 0 operations yields [1, 2]. x = 1 yields [0, 1]. x = 2 yields [1, 1]. x = 2 and then x = 1 yields [0, 0]. Notice that choosing x = 1 and then x = 1 will give [0, 0] which has been counted already. So, the number of different final arrays achievable is 4. Return 4 modulo (10^9 + 7) which equals 4. Function Description: Complete the function getCount in the editor below. getCount has the following parameters: int arr[n]: the original array Returns: int: the number of different final arrays achievable, modulo (10^9 + 7) Constraints: 1 ≤ n ≤ 10^5 0 ≤ arr[i] ≤ 10^5 Input Format For Custom Testing Sample Case 0 STDIN 3 2 1 Function: arr[] size n = 3, arr = [2, 1] Sample Output: 4 Explanation: The four possible final arrays are shown operation(s) -> result 0 operations -> [0, 2, 1] x = 1 -> [0, 1, 0] x = 2 -> [0, 1, 1] x = 2 then x = 1 -> [0, 0, 0] Sample Case 1 STDIN 4 2 3 0 2 Function: arr[] size n = 4, arr = [2, 3, 0, 2] Sample Output: 6 Explanation: No operations -> [2, 3, 0, 2] x = 1 -> [1, 2, 0, 1] x = 1 then x = 1 -> [0, 1, 0, 0] x = 1 then x = 2 -> [1, 1, 0, 1] x = 1, x = 2 then x = 1 -> [0, 0, 0, 0] x = 3 -> [2, 2, 0, 2]