{"blocks": [{"key": "77798c95", "text": "Question", "type": "header-two", "depth": 0, "inlineStyleRanges": [], "entityRanges": [], "data": {}}, {"key": "101ddb43", "text": "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 \u2264 s \u2264 9\u00b7\u2308log10 n\u2309), 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\u2019s time- and space-complexity.", "type": "unstyled", "depth": 0, "inlineStyleRanges": [], "entityRanges": [], "data": {}}, {"key": "428d51b2", "text": "\u200b", "type": "unstyled", "depth": 0, "inlineStyleRanges": [], "entityRanges": [], "data": {}}, {"key": "a6f8ce15", "text": "Hints", "type": "header-two", "depth": 0, "inlineStyleRanges": [], "entityRanges": [], "data": {}}, {"key": "6357ad81", "text": "Observe that only the frequency of each digit-sum matters; you do not need to materialize every coupon number.", "type": "unordered-list-item", "depth": 0, "inlineStyleRanges": [], "entityRanges": [], "data": {}}, {"key": "dac461e5", "text": "Think about how to compute digit sums efficiently for the range 1\u2026n.", "type": "unordered-list-item", "depth": 0, "inlineStyleRanges": [], "entityRanges": [], "data": {}}], "entityMap": {}}