Input: num = 0, k = 7
Output: 0
Explanation: The sum of an empty set is considered 0.

Constraints

0 <= num <= 3000
0 <= k <= 9

Solution

Approach

We want the minimum number of positive integers with units digit k that sum to num. Try all possible counts x (from 1 to 300, since num <= 3000), and check if num - k * x is non-negative and divisible by 10. If so, x is a valid answer. Return the smallest such x, or 0 if num == 0, or -1 if not possible.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minimumNumbers(int num, int k) {\n        if (num == 0) return 0;\n        for (int x = 1; x <= 300; ++x) {\n            if (num - k * x < 0) break;\n            if ((num - k * x) % 10 == 0) return x;\n        }\n        return -1;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minimumNumbers</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> num</span>&#

Related Tags