No Can Has Sum

Abstract

This is just a quick warm-up assignment to get you thinking algorithmically and to encourage you to think in terms of implementing clever, efficient solutions to problems. Its also a fairly gentle return to Java for those who havent used it in a while.

You might find this problem very tricky. Its important to struggle with it. Dont be discouraged if you dont solve it right away. Maybe walk away, take a break, and come back to it later (perhaps even the following day). You might be amazed by what your brain can do if you let it work on a problem in the background and/or if you come back to a problem wellrested, with a fresh perspective.

Please feel free to seek out help in office hours if youre lost, and remember that its okay to have conceptual discussions with other students about this problem, as long as youre not sharing code (or pseudocode). Keep in mind that youll benefit more from this problem if you struggle with it a bit before discussing it with anyone else.

Problem Statement

Given a sorted array of positive integers, array, find the smallest integer value p 1 such that no subset of elements from array sums to p. The array will be sorted in non-decreasing order. It may contain duplicates. For example:

Input:
{1, 1, 1, 1, 2}
{3, 4, 5}
{1, 2, 3, 4, 4}
{1, 3, 9}

Output:
7
1
15
2

Runtime Requirements

You must implement an O(n) solution to this problem in order to receive credit.

Method and Class Requirements

You must implement the following methods in a class named Program1:

public class Program1 { public static int NoCanHasSum(int [] array) {
// An O(n) method that returns the smallest integer p ≥ 1 // such that no subset of elements from array sums to p.
// array is an array of positive integers sorted in // non-decreasing order. The array may contain duplicates.
} public static double difficultyRating() {
// Return a double indicating how difficult you found this
// problem on a scale of 1.0 (ridiculously easy) through 5.0 // (insanely difficult).
// Please give your rating in terms of how you perceived the
// difficulty of this problem before discussing it with others // (if applicable).
} public static double hoursSpent() {
// Return an estimate (greater than zero) of the number // of hours you spent on this assignment.
}
}