Entering edit mode

**Avg CTC:** 18lpa

**Job Roles:** Developer, Sr Developer

**Location Available:** Pune, Bengaluru

**Job Link:** CITI careers page

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

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

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------------- -> 3 Decrease middle element to right one / / 2 2 / / 1 1 5 / \ / \ / \ 3-------3------- -> 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 < nums.size(); i++){
//decreasing sequence found
if(nums[i] < nums[i-1]){
//if count after increasing becomes more than 1 then false
if(++cnt > 1) return false;
//in case of the 2nd element as i[1] < i[0] so make i[0] = i[1]
if(i == 1 || nums[i-2] <= nums[i])
nums[i-1] = nums[i];
else
nums[i] = nums[i-1];
}
}
return true;
```

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)**

Loading Similar Posts