Katkat
Back

Lottery Coupon Winners Calculation

Goldman SachsProduct Manager · Online Assessment
MediumProduct ManagerOnline AssessmentProduct / Decision Making

Last updated

This question tests a candidate's ability to apply digit dynamic programming to efficiently count integers with specific digit-sum properties over large numeric ranges. It evaluates algorithmic thinking at the intersection of combinatorics and optimization, a category commonly assessed in technical interviews to measure comfort with non-obvious problem reductions and complexity trade-offs.

Question

You are given an integer n representing consecutively numbered lottery coupons from 1 to n. A person is considered a winner if the sum of the digits on their coupon equals a value s. Among all possible values of s (1 ≤ s ≤ 9·⌈log10 n⌉), determine how many distinct values of s yield the largest possible number of winners. Implement a function lotteryCoupons(n) that returns this count, and explain your algorithm’s time- and space-complexity.

​

Hints

Observe that only the frequency of each digit-sum matters; you do not need to materialize every coupon number.

Think about how to compute digit sums efficiently for the range 1…n.