Sum of Numbers With Units Digit K - Video Solutions

Problem Overview: You are given two integers num and k. The task is to find the minimum number of positive integers whose units digit equals k such that their total sum equals num. Each chosen number must end with digit k (for example: 7, 17, 27 if k = 7). If no such combination exists, return -1.

The key observation is that numbers with the same units digit behave predictably under addition. Only the last digit of the sum matters for feasibility. This turns the problem into a small search over possible counts instead of constructing the actual numbers.

Approach 1: Greedy Enumeration (O(1) time, O(1) space)

This approach relies on the repeating pattern of last digits when adding numbers that end with k. If you pick i numbers each ending with digit k, their combined units digit becomes (i * k) % 10. For the sum to equal num, the last digit must match num % 10. Because last digits repeat every 10 multiples, you only need to test values of i from 1 to 10.

For each candidate count i, check two conditions: the units digit requirement (i * k) % 10 == num % 10, and whether the total sum can reach num (i.e., i * k <= num). The second condition ensures the remaining value can be filled by adding tens to the chosen numbers, such as converting k into k + 10, k + 20, and so on. The first valid i is the minimum count. This method is effectively a constant-time greedy check combined with small enumeration.

Approach 2: Modular Arithmetic Optimization (O(1) time, O(1) space)

This version focuses directly on the modular equation governing the problem. If i numbers end with digit k, the final digit of the sum must satisfy (i * k) mod 10 = num mod 10. Instead of thinking about building numbers, you solve this as a modular arithmetic constraint. The smallest i that satisfies the equation and keeps i * k ≤ num gives the answer.

Because the modulus is 10, the search space is bounded to at most 10 candidates. This guarantees constant-time performance regardless of input size. The reasoning heavily uses properties from math and modular cycles, which is why this problem is categorized under mathematical reasoning rather than typical dynamic programming despite the combinational appearance.

Recommended for interviews: Interviewers expect the greedy enumeration or modular arithmetic insight. Brute-force construction of numbers shows understanding but wastes time. Recognizing that only the last digit matters reduces the problem to checking at most ten possibilities, which demonstrates strong number-pattern recognition and mathematical reasoning.