non-consstructible change algoexpert problem

tournament-winner problem

git-repo

solution

  public int nonConstructibleChange(int[] coins) {
    // O(nlogn) time | O(1) space - where n is the number of coins
		Arrays.sort(coins);
		int s = 0;
		for(int coin : coins){
			if(s+1<coin){
				return s+1;
			}
			s += coin;		
		}
    return s+1;
  }

We can solve this problem by adding up the coins and comparing the current sum to the next coin in the array. if the sum + 1 < coin then we can assume that sum + 1 cannot be made because the next value of the coin is too big and it will skip the immediate next couple values.