// The traveller has several coins. Find the minimum sum that he cannot pay without change.

// The function accepts array of coin’s face values sorted in non-descending order.

// Time: O(coins.Length)

using System;

public class Program

{     

    // given the sorted array arr[0..n-1] output the smallest sum that cannot be represented 

    // as sum of subset of elements, 1 being the smallest possible outcome

    static int MinImpossible(int [] coin) 

    {

        int i = 0;

        int r = 1;

        // invariant: r is the min sum that cannot be represented by coin[0..i-1]

        // and 0<=i<=coin.Length

        while (i < coin.Length && coin[i] <= r)

        {

            // coin[0..i-1] can represent a sum from 1 to r-1, 

            // adding coin[i] adds the range coin[i]..coint[i]+r-1

            // since coin[i] <= r the ranges can be joined into one range

            r += coin[i];

            i++;

        }

        // either all coins are used or next coin cannot close the gap

        return r;

    }

    public static void Main() 

    {

        Test(new int[0]);

        Test(new[]{ 2          });

        Test(new[]{ 1, 3       });

        Test(new[]{ 1, 2, 4    });

        Test(new[]{ 1, 1, 3, 7 });

    }

​

    public static void Test(int [] coin) 

    {

        Console.WriteLine("Coins ({0}) can't pay sum of {1}", string.Join(" ", coin), MinImpossible(coin));

    }

}

​