TopCoder problem "Gauss" used in SRM 151 (Division I Level Three)

Problem Statement

    Carl Friedrich Gauss (1777-1855) is considered to be one of the greatest mathematicians ever. There is a nice story about him being at elementary school: The teacher wanted to keep the class busy and assigned to them the task of adding all whole numbers from 1 to 100. While the other kids were just about to start their additions, Gauss already presented the result, 5050. He noticed that the numbers can be grouped into 50 pairs of value 101 (1+100, 2+99, ...), and from this he deduced that the sum of all natural numbers from 1 to n equals n(n+1)/2.

Now let's consider adding consecutive numbers not only starting at 1 but at any natural number. E.g. if you start at 13 and add three consecutive numbers, you get 13+14+15 = 42. Now can 42 also be achieved by adding two or more consecutive numbers starting at a different number? Yes, it can: 3+4+5+6+7+8+9 = 9+10+11+12 = 42.

Given a number target, return all intervals representing a sequence of two or more consecutive natural numbers (positive integers) that add up to target. The intervals have to be sorted by ascending lower interval limits. The interval representing the sequence a + (a+1) + ... + (b-1) + b is the String "[a, b]" (quotes for clarity; there is a single space between the comma and b).


Method signature:String[] whichSums(String target)
(be sure your method is public)


-The value of target fits into a long.


-target represents a natural number between 1 and 10^11, inclusive, without leading zeros.


Returns: { "[3, 9]",  "[9, 12]",  "[13, 15]" }
This is the example from the problem statement.
Returns: { }
There are no 2 or more consecutive natural numbers that add up to 4.
Returns: { "[8, 9]" }
Returns: { "[1, 10]",  "[9, 13]",  "[27, 28]" }

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Advanced Math, Search