Gauss
SRM 151 · 2003-06-17 · by Wernie
SRM 151 · 2003-06-17 · by Wernie · Advanced Math, Search
Problem Statement
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 theString "[a, b]" (quotes for clarity; there is a single space between the comma and b).
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
Notes
- The value of target fits into a long.
Constraints
- target represents a natural number between 1 and 10^11, inclusive, without leading zeros.
Examples
0)
"42"
Returns: { "[3, 9]", "[9, 12]", "[13, 15]" }
This is the example from the problem statement.
1)
"4"
Returns: { }
There are no 2 or more consecutive natural numbers that add up to 4.
2)
"17"
Returns: { "[8, 9]" }
3)
"55"
Returns: { "[1, 10]", "[9, 13]", "[27, 28]" }
4)
"1"
Returns: { }
Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Gauss with a public method vector<string> whichSums(string target) · 59 test cases · 2 s / 256 MB per case