Sum of Numbers With Units Digit K solution and explanation
9 more videos on this problem
Complete Weekly Contest 298 | Leetcode 2310 Sum of Numbers With Units Digit K | Live coding 🔥🔥Coding Decoded · 12:40 · 2K views
Leetcode 2310 Sum of Numbers With Units Digit KThinkCode · 4:49 · 2K views
2310. Sum of Numbers With Units Digit K (Leetcode Medium)Programming Live with Larry · 15:19 · 1K views
Leetcode Weekly contest 298 - Medium - Sum of Numbers With Units Digit KPrakhar Agrawal · 11:40 · 595 views
5218. Sum of Numbers With Units Digit K | Leetcode Weekly Contest SolutionContests All Correct (AC) Solutions · 1:04 · 590 views
LeetCode Weekly Contest 298 || 2309 2310 || LeetCode Weekly SolutionBinaryMagic · 25:43 · 522 views
2310. Sum of Numbers With Units Digit K | Leetcode 2310 | D.P (Memoization) | HindiCoke with Code · 17:10 · 440 views
Leetcode 2310 Sum of Numbers With Units Digit K Weekly contest 298 How to solve FAANG Coding HindiLeetcode Hindi · 8:38 · 159 views
LeetCode 2310 Sum of Numbers with Units Digit K[CE] Code Engineering · 20:11 · 85 views
2310. Sum of Numbers With Units Digit K | C++ | Medium | Math | LeetCodeMay We Code · 0:43 · 71 views
The 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.
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 <= 30000 <= 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.
def minimum_size(num, k):
if num == 0:
return 0
if k == 0 and num % 10 != 0:
return -1
min_size = num // k if k != 0 else float('inf')
if k != 0:
for n in range(min_size, 0, -1):
if (num - n * k) % 10 == 0:
return n
return -1
# Example usage:
# print(minimum_size(58, 9)) # Output: 2
# print(minimum_size(37, 2)) # Output: -1
# print(minimum_size(0, 7)) # Output: 0public class MinimumSize {
public static int minimumSize(int num, int k) {
if (num == 0) return 0;
if (k == 0 && num % 10 != 0) return -1;
int minSize = k != 0 ? num / k : 0;
for (int n = minSize; n > 0; n--) {
if ((num - n * k) % 10 == 0) {
return n;
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(minimumSize(58, 9)); // 2
System.out.println(minimumSize(37, 2)); // -1
System.out.println(minimumSize(0, 7)); // 0
}
}#include <iostream>
int minimum_size(int num, int k) {
if (num == 0) return 0;
if (k == 0 && num % 10 != 0) return -1;
int min_size = k ? num / k : 0;
for (int n = min_size; n > 0; --n) {
if ((num - n * k) % 10 == 0) {
return n;
}
}
return -1;
}
int main() {
std::cout << minimum_size(58, 9) << std::endl; // 2
std::cout << minimum_size(37, 2) << std::endl; // -1
std::cout << minimum_size(0, 7) << std::endl; // 0
return 0;
}function minimumSize(num, k) {
if (num === 0) return 0;
if (k === 0 && num % 10 !== 0) return -1;
let minSize = k ? Math.floor(num / k) : 0;
for (let n = minSize; n > 0; n--) {
if ((num - n * k) % 10 === 0) {
return n;
}
}
return -1;
}
console.log(minimumSize(58, 9)); // Output: 2
console.log(minimumSize(37, 2)); // Output: -1
console.log(minimumSize(0, 7)); // Output: 0;#include <stdio.h>
int minimum_size(int num, int k) {
if (num == 0) return 0;
if (k == 0 && num % 10 != 0) return -1;
int min_size = k ? num / k : 0;
for (int n = min_size; n > 0; --n) {
if ((num - n * k) % 10 == 0) {
return n;
}
}
return -1;
}
int main() {
printf("%d\n", minimum_size(58, 9)); // Output: 2
printf("%d\n", minimum_size(37, 2)); // Output: -1
printf("%d\n", minimum_size(0, 7)); // Output: 0
return 0;
}using System;
class Program {
static int MinimumSize(int num, int k) {
if (num == 0) return 0;
if (k == 0 && num % 10 != 0) return -1;
int minSize = k != 0 ? num / k : 0;
for (int n = minSize; n > 0; n--) {
if ((num - n * k) % 10 == 0) {
return n;
}
}
return -1;
}
static void Main() {
Console.WriteLine(MinimumSize(58, 9)); // 2
Console.WriteLine(MinimumSize(37, 2)); // -1
Console.WriteLine(MinimumSize(0, 7)); // 0
}
}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.
Time Complexity: O(num/k) in the worst case scenario.
Space Complexity: O(1).
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.
def minimum_size_modular(num, k):
if num == 0:
return 0
if k == 0 and num % 10 != 0:
return -1
for n in range(1, 101): # The max is theoretically num//k + 1 at most 300
if (num - n * k) % 10 == 0:
return n
return -1
# Example usage:
# print(minimum_size_modular(58, 9)) # Output: 2
# print(minimum_size_modular(37, 2)) # Output: -1
# print(minimum_size_modular(0, 7)) # Output: 0public class MinimumSizeModular {
public static int minimumSizeModular(int num, int k) {
if (num == 0) return 0;
if (k == 0 && num % 10 != 0) return -1;
for (int n = 1; n <= 100; n++) {
if ((num - n * k) % 10 == 0) {
return n;
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(minimumSizeModular(58, 9)); // 2
System.out.println(minimumSizeModular(37, 2)); // -1
System.out.println(minimumSizeModular(0, 7)); // 0
}
}#include <iostream>
int minimum_size_modular(int num, int k) {
if (num == 0) return 0;
if (k == 0 && num % 10 != 0) return -1;
for (int n = 1; n <= 100; ++n) {
if ((num - n * k) % 10 == 0) {
return n;
}
}
return -1;
}
int main() {
std::cout << minimum_size_modular(58, 9) << std::endl; // 2
std::cout << minimum_size_modular(37, 2) << std::endl; // -1
std::cout << minimum_size_modular(0, 7) << std::endl; // 0
return 0;
}function minimumSizeModular(num, k) {
if (num === 0) return 0;
if (k === 0 && num % 10 !== 0) return -1;
for (let n = 1; n <= 100; n++) {
if ((num - n * k) % 10 === 0) {
return n;
}
}
return -1;
}
console.log(minimumSizeModular(58, 9)); // Output: 2
console.log(minimumSizeModular(37, 2)); // Output: -1
console.log(minimumSizeModular(0, 7)); // Output: 0;#include <stdio.h>
int minimum_size_modular(int num, int k) {
if (num == 0) return 0;
if (k == 0 && num % 10 != 0) return -1;
for (int n = 1; n <= 100; ++n) {
if ((num - n * k) % 10 == 0) {
return n;
}
}
return -1;
}
int main() {
printf("%d\n", minimum_size_modular(58, 9)); // Output: 2
printf("%d\n", minimum_size_modular(37, 2)); // Output: -1
printf("%d\n", minimum_size_modular(0, 7)); // Output: 0
return 0;
}using System;
class Program {
static int MinimumSizeModular(int num, int k) {
if (num == 0) return 0;
if (k == 0 && num % 10 != 0) return -1;
for (int n = 1; n <= 100; n++) {
if ((num - n * k) % 10 == 0) {
return n;
}
}
return -1;
}
static void Main() {
Console.WriteLine(MinimumSizeModular(58, 9)); // 2
Console.WriteLine(MinimumSizeModular(37, 2)); // -1
Console.WriteLine(MinimumSizeModular(0, 7)); // 0
}
}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.
Time Complexity: O(10).
Space Complexity: O(1).
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).
function minimumNumbers(num: number, k: number): number {
if (!num) return 0;
let digit = num % 10;
for (let i = 1; i < 11; i++) {
let target = i * k;
if (target <= num && target % 10 == digit) return i;
}
return -1;
}func minimumNumbers(num int, k int) int {
if num == 0 {
return 0
}
for i := 1; i <= num; i++ {
t := num - k*i
if t >= 0 && t%10 == 0 {
return i
}
}
return -1
}Approach 4: Default Approach
func minimumNumbers(num int, k int) int {
if num == 0 {
return 0
}
for i := 1; i <= 10; i++ {
if (k*i)%10 == num%10 && k*i <= num {
return i
}
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(num/k) in the worst case scenario. |
| Modular Arithmetic Optimization | Time Complexity: O(10). |
| Math + Enumeration | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Enumeration | O(1) | O(1) | Best general solution. Quickly test counts from 1–10 based on units digit behavior. |
| Modular Arithmetic Optimization | O(1) | O(1) | When reasoning mathematically about the equation (i * k) mod 10 = num mod 10. |
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.