SumK
SRM 112 · 2002-09-06 · by dgoodman
SRM 112 · 2002-09-06 · by dgoodman
Problem Statement
Problem Statement
Some numbers can be expressed as the sum of k consecutive numbers. 9 = -1 + 0 + 1 + 2 + 3 + 4 so 9 can be expressed as the sum of 6 consecutive numbers. Your program will be given a collection of values and a positive k, and it will report how many of the values in the collection could be expressed as the sum of k consecutive numbers.
Notes
- If a value is repeated, count it each time it appears if it is a sum of k.
- Values may be negative or zero, but k will be positive.
Constraints
- k is between 1 and 1,000,000,000 (inclusive)
- each element in values is between -1,000,000,000 and 1,000,000,000 (inclusive)
- the number of elements in values is between 0 and 50 (inclusive)
Examples
0)
3
{-987,5,0}
Returns: 2
-987 = -330 + -329 + -328, 5 is not the sum of 3 consecutive values, 0 = -1 + 0 + 1
1)
1000
{0,-500,499500,499501,17,-500}
Returns: 3
-500 + -499 + ... + 499 = -500, 0 + 1 + ... + 999 = 499500, and neither 499501 nor 17 nor 0 can be expressed as the sum of 1000 consecutive values. (-500 is counted twice since it appears twice in values.)
2)
1
{3,4,5,-1000000000}
Returns: 4
Each value is the sum of itself
3)
2
{}
Returns: 0
4)
2
{-999999999}
Returns: 1
Submissions are judged against all 17 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SumK with a public method int count(int k, vector<int> values) · 17 test cases · 2 s / 256 MB per case