InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Algorithm to find the smallest integer value that can't be represented as sum of any subset of a given array. |
|
Answer» Given a SORTED array (sorted in non-decreasing order) of positive numbers, FIND the smallest positive integer VALUE that cannot be represented as sum of elements of any subset of given set. Expected time complexity is O(n).Examples:Input: arr[] = {1, 3, 6, 10, 11, 15};Output: 2Input: arr[] = {1, 1, 1, 1};Output: 5Input: arr[] = {1, 1, 3, 4};Output: 10Input: arr[] = {1, 2, 5, 10, 20, 40};Output: 4Input: arr[] = {1, 2, 3, 4, 5, 6};Output: 22... |
|