Sum of Numbers With Units Digit K - Practice Coding Problems

Sum of Numbers With Units Digit K - Problem

Given two integers num and k, consider a set of positive integers with the following properties:

The units digit of each integer is k.
The sum of the integers is num.

Return the minimum possible size of such a set, or -1 if no such set exists.

Note:

The set can contain multiple instances of the same integer, and the sum of an empty set is considered 0.
The units digit of a number is the rightmost digit of the number.

Input & Output

Example 1 — Basic Case

$ Input: num = 58, k = 9

› Output: 2

💡 Note: We can use two numbers: 19 and 39. Both end in 9 and 19 + 39 = 58. This is the minimum possible size.

Example 2 — Single Number

$ Input: num = 37, k = 2

› Output: -1

💡 Note: No combination of positive numbers ending in 2 can sum to 37 (which ends in 7). Numbers ending in 2 create sums ending in even digits only.

Example 3 — Zero Sum

$ Input: num = 0, k = 7

› Output: 0

💡 Note: Empty set has sum 0, so we need 0 numbers.

Constraints

0 ≤ num ≤ 3000
0 ≤ k ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input

Target sum num=58, required units digit k=9

Process

Find minimum numbers ending in 9 that sum to 58

Output

Return count=2 (using 19+39=58)

Key Takeaway

🎯 Key Insight: The units digit pattern of sums repeats every 10 numbers, enabling O(1) solution

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that the units digit pattern repeats every 10 numbers, so we only need to check counts 1-10. Best approach uses modular arithmetic for O(1) time complexity. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(num)	O(1)	Try all possible counts from 1 to num, checking if valid sum exists
Mathematical Optimization	O(1)	O(1)	Use modular arithmetic to directly calculate minimum count

Brute Force Enumeration — Algorithm Steps

Try count from 1 to num
For each count, check if (num - count*k) is divisible by 10
Return first valid count or -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Count 1

Check if 1 number can sum to target

Try Count 2

Check if 2 numbers can sum to target

Found Valid

Return first valid count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int num, int k) {
    if (num == 0) {
        return 0;
    }
    
    // Try each possible count of numbers
    for (int count = 1; count <= num; count++) {
        // Minimum sum with count numbers ending in k
        int minSum = count * k;
        if (minSum > num) {
            break;
        }
        
        // Check if we can reach num by adding multiples of 10
        int remaining = num - minSum;
        if (remaining >= 0 && remaining % 10 == 0) {
            return count;
        }
    }
    
    return -1;
}

int main() {
    int num, k;
    scanf("%d", &num);
    scanf("%d", &k);
    int result = solution(num, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(num)

Loop through all possible counts from 1 to num

✓ Linear Growth

Space Complexity

O(1)

Only using constant variables

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler