Question: Give a set of coins denoted by an integer array a. a[i] is the value of the i-th coin which can be any integer. Find the minimal number of missing coins (whose value can be any integer) such that we can get any exact change from 1 to N by choosing from the new set of coins.
Example: If a = [1, 5] N=10, the missing coins in a are 2 and 4 because a subset of [1, 2, 4, 5] can be summed to any integer from 1 to 10. Thus, the answer is 2.
===========
Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33021821.html
Example: If a = [1, 5] N=10, the missing coins in a are 2 and 4 because a subset of [1, 2, 4, 5] can be summed to any integer from 1 to 10. Thus, the answer is 2.
===========
Ref
[1] http://www.mitbbs.com/article_t/JobHunting/33021821.html
No comments:
Post a Comment