DSA interview question

Count Number of Nice Subarrays

Hard · Algorithms · Topics: sliding window, prefix sum, array

The problem

A game rewards a player whenever a contiguous run of turns contains exactly k odd dice rolls. Given the sequence of rolls, count the "nice" subarrays with exactly k odd numbers. Only parity matters, so map each value to 1 (odd) or 0 (even), and the task becomes "subarrays whose sum is exactly k". That's the same atMost(k) − atMost(k − 1) sliding-window trick as binary subarrays with a given sum.

Example: [1, 1, 2, 1, 1], k = 3 → 2 ([1,1,2,1] and [1,2,1,1]).

Function signature

long long numberOfSubarrays(const vector<int>& nums, int k);

Test cases

Input `(nums, k)`	Output	Explanation
`([1, 1, 2, 1, 1], 3)`	`2`
`([2, 4, 6], 1)`	`0`	No odd numbers
`([2, 2, 2, 1, 2, 2, 1, 2, 2, 2], 2)`	`16`	4 choices of start × 4 choices of end
`([1, 2, 3], 1)`	`4`	[1], [1,2], [2,3], [3]
`([1], 1)`	`1`

(Confirm: values are positive integers; subarrays are contiguous and non-empty; k ≥ 1.)

How interviewers phrase it

"A continuous subarray is nice if there are k odd numbers in it. Return the number of nice subarrays" (LeetCode 1248).

Clarifying questions to ask

Exactly k odd numbers? (Yes.)
Do even numbers matter otherwise? (No.)
How large is n? (Up to 5·10⁴; the count can be large, so use 64-bit.)

Follow-ups to expect

"How does this map to a known problem?"
"Why atMost(k) − atMost(k − 1)?"
"Alternative O(n) solutions?"
"Why does the third testcase give 16?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview