CODEWITHSUNDEEP
arrayssummax
Brij Raj Kishore
Brij Raj Kishore

Reputation: 1705

maximum no. of elements in an array having sum less than or equal to k

I want to find the maximum no. of elements in a given positive integer array such that their sum is less than or equal to a given no. k. For example, I have an array 

[3,4,7,2,6,5,1] and k=6;

The Answer is 3 as 1,2,3 are maximum elements to give sum 6.

Upvotes: 6

Views: 7481

Answers (3)

sakigo
sakigo

Reputation: 113

int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(), costs.end());
        int ret = 0;
        for (auto p : costs) if (coins >= p) {
            coins -= p;
            ret++;
        }
        return ret;
    }

Upvotes: 0

DJohnson
DJohnson

Reputation: 919

A more 'Swifty' way might be:

var maxSum = 6
var newSum = 0

let maxElements = [3,4,7,2,6,5,1].sort().filter() {
       if $0 + newSum <= maxSum {
          newSum += $0
          return true
       }
       return false
    } .count    //returns 3

Upvotes: 1

chiliNUT
chiliNUT

Reputation: 19573

Sort the array, count the number of elements, then start summing elements sequentially until their sum is greater than k or you have gone through each element, then subtract 1 from the count if the sum is greater than k

Pseudocode:

    let k=6
    sort the array
    [1,2,3,4,5,6,7]
    let sum=0
    let count=7 //(7 elements in the array)
    for (i=0;i<7;i++) {
        sum+=array[i];
        if (sum>k)
            break;
    }
    if (sum>k)
    i--;

i is the max number of elements.

Upvotes: 7

Related Questions