How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Count k for consecutive-sum generator | Microsoft Coding Question

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.

Input: (15,)

Expected Output: 4

Explanation: k=15 ([15]), k=7 ([7,8]), k=4 ([4,5,6]), and k=1 ([1,2,3,4,5]) all sum to 15.

Input: (9,)

Expected Output: 3

Explanation: k=9 ([9]), k=4 ([4,5]), and k=2 ([2,3,4]) sum to 9.

Input: (5,)

Expected Output: 2

Explanation: k=5 ([5]) and k=2 ([2,3]) sum to 5.

Input: (16,)

Expected Output: 1

Explanation: 16 is a power of two, so only the trivial k=16 ([16]) works; no run of two or more consecutive integers sums to 16.

Input: (3,)

Expected Output: 2

Explanation: k=3 ([3]) and k=1 ([1,2]) sum to 3.

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.

Quick Overview

This question evaluates number-theoretic reasoning and understanding of arithmetic progressions, focusing on how sums of consecutive positive integers can be characterized and counted.