Minimum count of numbers required from given array to represent S

user_3181365 0
Viewed 569

Given an integer S and an array arr[], the task is to find the minimum number of elements whose sum is S, such that an element of the array can be chosen only once to get sum S.

Example:

Input: arr[] = {25, 10, 5}, S = 30 
Output: 2

Explanation:

Minimum possible solution is 2, (25+5)

Example:

Input: arr[] = {2, 1, 4, 3, 5, 6}, Sum= 6 
Output: 1

Explanation:

Minimum possible solution is 1, (6)

I have found similar solution here but it says element of array can be used multiple times.

I have this code from the link which uses an array element multiple times, but how to restrict this to use only once?

static int Count(int S[], int m, int n)
{
    int [][]table = new int[m + 1][n + 1];
 
    // Loop to initialize the array
    // as infinite in the row 0
    for(int i = 1; i <= n; i++)
    {
    table[0][i] = Integer.MAX_VALUE - 1;
    }
 
    // Loop to find the solution
    // by pre-computation for the
    // sequence
    for(int i = 1; i <= m; i++)
    {
    for(int j = 1; j <= n; j++)
    {
        if (S[i - 1] > j)
        {
            table[i][j] = table[i - 1][j];
        }
        else
        {
                 
            // Minimum possible for the
            // previous minimum value
            // of the sequence
            table[i][j] = Math.min(table[i - 1][j],
                            table[i][j - S[i - 1]] + 1);
        }
    }
    }
    return table[m][n];
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 9, 6, 5, 1 };
    int m = arr.length;
     
    System.out.print(Count(arr, m, 11));
}
arrays algorithm java
1 Answers

The idiomatic approach for this is to loop backwards when updating the table of previous results.

static int minElementsForSum(int[] elems, int sum){
    int[] minElems = new int[sum + 1];
    for(int i = 1; i <= sum; i++) minElems[i] = Integer.MAX_VALUE;
    for(int elem: elems) 
        for(int i = sum; i >= elem; i--) 
            if(minElems[i - elem] != Integer.MAX_VALUE) 
              minElems[i] = Math.min(minElems[i], minElems[i - elem] + 1);
    return minElems[sum];
}

Demo

user_95131840
Related