CSES Solutions – Missing Coin Sum
You have N coins with positive integer values. What is the smallest sum you cannot create using a subset of the coins?
Examples:
Input: N = 5, coins[] = {2, 9, 1, 2, 7}
Output: 6
Explanation:
- Sum = 1, we can take the coin with value 1.
- Sum = 2, we can take the coin with value 2.
- Sum = 3, we can take coins with value 1 and 2.
- Sum = 4, we can take coins with value 2 and 2.
- Sum = 5, we can take coins with value 1, 2 and 2.
- Sum = 6, no possible subset of coins can sum up to 6.
Input: N = 3, coins[] = {1, 2, 3}
Output: 7
Explanation:
- Sum = 1, we can take the coin with value 1.
- Sum = 2, we can take the coin with value 2.
- Sum = 3, we can take coins with value 3.
- Sum = 4, we can take coins with value 1 and 3.
- Sum = 5, we can take coins with value 2 and 3.
- Sum = 6, we can take coins with value 1, 2 and 3.
- Sum = 7, no possible subset of coins can sum up to 7.
Approach: To solve the problem, follow the below idea:
The problem can be solved by using Greedy approach. We can start from the smallest value coin and move to higher values. The main idea is to start from the coins of smallest value and build up the sum of coins we can form. Let’s say we have some coins whose total value is X, so the maximum value of the next coin can be X + 1. If the next coin has a value greater than X + 1 then (X + 1) is the smallest sum which we cannot create using any subset of coins. Otherwise, if the value of the next coin is less than (X + 1) we can add it to the total value to get the new total sum X.
Step-by-step algorithm:
- Sort the array of coins in increasing order of values.
- Maintain a variable X which stores the maximum value of the next coin.
- Iterate from 0 to N – 1, and check if arr[i] > X or not.
- If arr[i] > X, return X as the answer.
- Else if arr[i] <= X, update X = X + arr[i].
- After all the iterations if we haven’t returned yet, return (X + 1) as the answer.
C++
#include <bits/stdc++.h> #define ll long long using namespace std; // Function to find the maximum sum which we cannot // construct using given coins ll solve(ll* arr, ll N) { // Variable to store the maximum value of the next coin ll X = 1LL; // Sort the coins in ascending order of their values sort(arr, arr + N); for ( int i = 0; i < N; i++) { // If the current coin's value is greater than X, // then X is the answer if (arr[i] > X) { return X; } // If current coin's value is less than or equal to // X, then we can update X as X + arr[i] X += arr[i]; } return X; } int main() { // Sample Input ll N = 5; ll arr[] = { 2, 9, 1, 2, 7 }; cout << solve(arr, N); } |
Java
import java.util.Arrays; public class MaximumSumNotConstructible { // Function to find the maximum sum which we cannot // construct using given coins static long solve( long [] arr, int N) { // Variable to store the maximum value of the next coin long X = 1 ; // Sort the coins in ascending order of their values Arrays.sort(arr); for ( int i = 0 ; i < N; i++) { // If the current coin's value is greater than X, // then X is the answer if (arr[i] > X) { return X; } // If current coin's value is less than or equal to // X, then we can update X as X + arr[i] X += arr[i]; } return X; } public static void main(String[] args) { // Sample Input int N = 5 ; long [] arr = { 2 , 9 , 1 , 2 , 7 }; System.out.println(solve(arr, N)); } } // This code is contributed by rambabuguphka |
Python
# Function to find the maximum sum which we cannot # construct using given coins def solve(arr, N): # Variable to store the maximum value of the next coin X = 1 # Sort the coins in ascending order of their values arr.sort() for coin in arr: # If the current coin's value is greater than X, # then X is the answer if coin > X: return X # If current coin's value is less than or equal to # X, then we can update X as X + coin X + = coin return X if __name__ = = "__main__" : # Sample Input N = 5 arr = [ 2 , 9 , 1 , 2 , 7 ] print (solve(arr, N)) |
C#
using System; class Program { // Function to find the maximum sum which we cannot // construct using given coins static long Solve( long [] arr, long N) { // Variable to store the maximum value of the next coin long X = 1; // Sort the coins in ascending order of their values Array.Sort(arr); for ( int i = 0; i < N; i++) { // If the current coin's value is greater than X, // then X is the answer if (arr[i] > X) { return X; } // If the current coin's value is less than or equal to // X, then we can update X as X + arr[i] X += arr[i]; } return X; } static void Main() { // Sample Input long N = 5; long [] arr = { 2, 9, 1, 2, 7 }; Console.WriteLine(Solve(arr, N)); } } |
Javascript
// Function to find the maximum sum which we cannot // construct using given coins function solve(arr) { // Variable to store the maximum value of the next coin let X = 1; // Sort the coins in ascending order of their values arr.sort((a, b) => a - b); for (let i = 0; i < arr.length; i++) { // If the current coin's value is greater than X, // then X is the answer if (arr[i] > X) { return X; } // If current coin's value is less than or equal to // X, then we can update X as X + arr[i] X += arr[i]; } return X; } // Sample Input let arr = [2, 9, 1, 2, 7]; console.log(solve(arr)); // This code is contributed by Ayush Mishra |
6
Time Complexity: O(N), where N is the number of coins.
Auxiliary Space: O(1)
Contact Us