Skip to main content
Talentd

Sum of Numbers With Units Digit K - Solution & Explanation

MediumMathDynamic ProgrammingGreedyEnumeration17 min read
Practice this problem

Problem Statement

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.

 

Example 1:

Input: num = 58, k = 9
Output: 2
Explanation:
One valid set is [9,49], as the sum is 58 and each integer has a units digit of 9.
Another valid set is [19,39].
It can be shown that 2 is the minimum possible size of a valid set.

Example 2:

Input: num = 37, k = 2
Output: -1
Explanation: It is not possible to obtain a sum of 37 using only integers that have a units digit of 2.

Example 3:

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

 

Constraints:

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

Approach Overview

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.

Approach 1: Greedy Approach

In this approach, we attempt to find the minimum number of integers with unit digit k such that their sum equals num. Start by considering the maximum number with unit's digit k that can fit into num and proceed backward, diminishing the count only when absolutely necessary.

In this Python solution, the problem is approached by considering the number of integers with unit k that can sum up to num. It starts from the maximum potential solution and backtracks checking if a solution is feasible for smaller sizes. The process iterates through possible numbers and evaluates if the residual can be zero.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(num/k) in the worst case scenario.
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Modular Arithmetic Optimization

This approach leverages modular arithmetic by quickly checking conditions that ensure k-mod is consistent with achievable sums. Special cases are addressed directly, such as where k=0 but num is non-zero which is catchable by observing the remainder when dividing num by 10.

Here, we explore candidates under defined conditions until an effectual answer is determined. Iterating integers with incremental minimal inspection is central before uncovering a defined solution.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(10).
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Math + Enumeration

Each number that meets the splitting condition can be represented as 10x_i + k. If there are n such numbers, then num - n times k must be a multiple of 10.

We enumerate n from small to large, and find the first n that satisfies num - n times k being a multiple of 10. Since n cannot exceed num, the maximum value of n is num.

We can also only consider the units digit. If the units digit satisfies the condition, the higher digits can be arbitrary.

The time complexity is O(n), where n is the size of num. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(num/k) in the worst case scenario.
Space Complexity: O(1).

Modular Arithmetic Optimization

Time Complexity: O(10).
Space Complexity: O(1).

Math + Enumeration—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy EnumerationO(1)O(1)Best general solution. Quickly test counts from 1–10 based on units digit behavior.
Modular Arithmetic OptimizationO(1)O(1)When reasoning mathematically about the equation (i * k) mod 10 = num mod 10.

Video Solution

Complete Weekly Contest 298 | Leetcode 2310 Sum of Numbers With Units Digit K | Live coding 🔥🔥 • Coding Decoded • 2,341 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Numbers With Units Digit K easy or hard?
The problem is rated Medium because the trick is recognizing the repeating pattern of units digits under multiplication. Once you reduce the problem to modular arithmetic and a bounded enumeration of 10 cases, the implementation becomes straightforward.
Sum of Numbers With Units Digit K Python/Java solution
In Python or Java, the solution simply loops from i = 1 to 10 and checks if (i * k) % 10 equals num % 10 and i * k ≤ num. If a valid i is found, return it; otherwise return -1. The implementation is only a few lines and runs in constant time.
How to solve Sum of Numbers With Units Digit K in O(1)?
Use the equation (i * k) % 10 = num % 10. Iterate i from 1 to 10 and check whether the units digit condition holds and whether i * k ≤ num. Once a valid i is found, it represents the minimum number of integers ending with digit k needed to form num.
What is the best approach for Sum of Numbers With Units Digit K?
The best approach is a greedy enumeration based on modular arithmetic. You test counts from 1 to 10 and check whether (i * k) % 10 equals num % 10 and i * k ≤ num. Because the last digit cycle repeats every 10 multiples, this guarantees the minimum valid count in constant time O(1).
Is Sum of Numbers With Units Digit K asked at Google/Amazon/Meta?
This problem reflects the type of mathematical reasoning and modular arithmetic questions often used in interviews at companies like Google, Amazon, and Meta. It tests pattern recognition, number properties, and the ability to reduce a problem to a small bounded search.
What data structure is used in Sum of Numbers With Units Digit K?
No specialized data structure is required. The solution relies purely on arithmetic operations and modular checks. The logic revolves around number properties rather than arrays, hash maps, or trees.
What is the time complexity of Sum of Numbers With Units Digit K?
The optimal solution runs in O(1) time and O(1) space. Only up to 10 candidate counts are checked due to the repeating cycle of last digits modulo 10. No arrays, dynamic programming tables, or extra data structures are required.

Ready to solve this problem?

Practice Sum of Numbers With Units Digit K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Integers With Even Digit Sum

Next

Digit Count in Range