2310. Sum of Numbers With Units Digit K

📝 Problem Details

• Title: 2310. Sum of Numbers With Units Digit K
• Link: https://leetcode.com/problems/sum-of-numbers-with-units-digit-k/
• Difficulty: Medium
• Tags/Categories: Math Greedy

💭What Were My Initial Thoughts?

- valid numbers:
	- the numbers we can use must have a units digit of k
	- this means we can pick numbers like k, 10 + k, 20 + k, ..., m * 10 + k as long as they sum to num

- mathematical reformulation
	- we need to check if there exists some number of k-values that sum to num
	- since k has a fixed last digit, the sum must be possible when considering num mod 10

- optimization
	- instead of brute force checking all possible combinations, we only need to check multiples of 10 + k that are <= num

🤔What Did I Struggle With?

💡 Explanation of Solution

1. check smallest contribution first
	- start with the smallest value k (as term 1)
	- if num is already divisible by k, return 1

2. try multiples of 10
	- start with k, then try 10 + k, 20 + k, 30 + k ....
	- if at any point the remaining sum (num - x) is divisible by 10, we have found a valid solution
	- keep track of the minimum number of terms

3. terminate early 
	- since we only need numbers <= num, we stop when we surpass num

⌛ Complexity Analysis

Time Complexity: O(1)
- the loop runs at most 10 times 

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (num == 0) return 0; // edge case: if num is 0, no numbers are needed
 
        for(int i = 1; i <= 10; i++) { // check up to 10 multiples of k
            int x = i * k;  // possible sum using i numbers with last digit k
            if(x > num) break; // if sum exceeds num, stop
            if((num - x) % 10 == 0) return i;
        }
 
        return -1;
    }
};