Minimum Elements

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
286 upvotes
Asked in companies
ShareChatIBMCogoport

Problem statement

You are given an array of ‘N’ distinct integers and an integer ‘X’ representing the target sum. You have to tell the minimum number of elements you have to take to reach the target sum ‘X’.

Note: 
You have an infinite number of elements of each type.
For example 
If N=3 and X=7 and array elements are [1,2,3]. 
Way 1 - You can take 4 elements  [2, 2, 2, 1] as 2 + 2 + 2 + 1 = 7.
Way 2 - You can take 3 elements  [3, 3, 1] as 3 + 3 + 1 = 7.
Here, you can see in Way 2 we have used 3 coins to reach the target sum of 7.
Hence the output is 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T’, denoting the number of test cases.

The first line of each test case will contain two space-separated integers ‘N’ and ‘X’, denoting the size of the array and the target sum.

The second line of each test case contains ‘N’ space-separated integers denoting elements of the array.
Output Format : 
For each test case, print the minimum number of coins needed to reach the target sum ‘X’, if it's not possible to reach to target then print "-1".

Print a separate line for each test case.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 15
1 <= nums[i] <= (2^31) - 1
1 <= X <= 10000

All the elements of the “nums” array will be unique.
Time limit: 1 sec
Sample Input 1 :
2
3 7
1 2 3
1 0
1
Sample output 1 :
 3
 0
Explanation For Sample Output 1:
For the first test case,
Way 1 - You can take 4 elements  [2, 2, 2, 1] as 2 + 2 + 2 + 1 = 7.
Way 2 - You can take 3 elements  [3, 3, 1] as 3 + 3 + 1 = 7.
Here, you can see in Way 2 we have used 3 coins to reach the target sum of 7.
Hence the output is 3.
For the second test case
To reach X = 0, you don’t need to take any elements from the array.
The sum is already 0, so the total number of elements used is 0.
Sample Input 2 :
2
3 4
12 1 3
2 11
2 1
Sample output 2 :
2
6
Hint

Check for every possible way such that the sum is ‘X’.

Approaches (3)
Brute Force (Recursion)

The basic idea is to go over recursively to find the way such that the sum of chosen elements is ‘X’. For every element, we have two choices

 

1. Include the element in our set of chosen elements.

2. Don’t include the element in our set of chosen elements.

 

When we include an element in the set then we decrease the ‘X’ by the value of the element at the end. At any point, if we have X=0 then we can say that we have found the set of integers such that the sum of the set is equal to ‘X’.

 

Let us define a function “minimum( sum, num)”, where “sum” is the remaining sum that we have to make, “num” is the array that is given to us. Each time we have ‘n’ elements from which we have to take one.

If the function “minimum( sum, num)” returns INT_MAX which means that we cannot make the target sum ‘X’. 

 

Here is the algorithm:

  • minimum function:
    • If sum is less than 0
      • return INT_MAX
    • If sum is 0
      • Return 0
    • Declare an integer variable “ans” and initialize it with INT_MAX.
    • Iterate over n(say ‘j’)
      • Update ans as ans=min(ans ,1+ minimum(sum-num[j],  num))
    • Return ans
  • given function:
    • ans= numberOfWays( X, n, num).
    • If ans == INT_MAX
      • Return -1

                   Return ans

Time Complexity

O( N^X ), where ‘X’ is the target sum and ‘N’ is the size of the array.

 

Each time we have ‘n’ options from which we have to select one and in the worst-case ‘X’ is decreased by 1 each time. So, if you try to make the recursive tree you can see each time there will be ‘n’ recursive call generated.

So time complexity will be O( N^X ).

Space Complexity

O(X), where ‘X’ is the sum which we want.

 

The recursive stack for the “minimum” function can contain at most “X”. Therefore, the overall space complexity will be O(X).

Code Solution
(100% EXP penalty)
Minimum Elements
Full screen
Console