Count k for consecutive-sum generator
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
An array generator service produces a consecutive-integers array starting at a positive integer k: [k, k+1, ..., k+m−1] for some m ≥ 1. The service returns such an array if its sum equals a given positive integer s. Given s, determine how many distinct k values admit at least one valid array. Provide an algorithm, prove correctness, and analyze time and space complexity. For example, when s = 10, valid k are 1 and 10.
Quick Answer: This question evaluates number-theoretic reasoning and understanding of arithmetic progressions, focusing on how sums of consecutive positive integers can be characterized and counted.
An array generator service produces a consecutive-integers array starting at a positive integer k: [k, k+1, ..., k+m-1] for some m >= 1. The service returns such an array only if its sum equals a given positive integer s.
Given s, determine how many distinct positive integer values of k admit at least one valid array (i.e., for how many k does there exist some length m >= 1 with k + (k+1) + ... + (k+m-1) = s).
Example: for s = 10, the valid k are 1 (from [1,2,3,4]) and 10 (from [10]), so the answer is 2.
Write a function countK(s) that returns this count.
Constraints
- 1 <= s <= 10^9
- k is a positive integer (k >= 1)
- m, the array length, is >= 1
Examples
Input: (10,)
Expected Output: 2
Explanation: k=1 gives [1,2,3,4] (sum 10) and k=10 gives [10] (sum 10).
Input: (1,)
Expected Output: 1
Explanation: Only k=1 with the single-element array [1] sums to 1.
Hints
- The sum of [k, k+1, ..., k+m-1] equals m*k + m*(m-1)/2. Set this equal to s.
- For each candidate length m, k = (s - m*(m-1)/2) / m. A valid k exists iff the numerator is positive and divisible by m. Distinct m give distinct k, so just count the valid m.
- Stop iterating m once m*(m-1)/2 >= s, which gives an O(sqrt(s)) loop.