We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Numbers With Units Digit K

Number: 1334

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two integers num and k, determine the minimum number of positive integers (where each integer ends with the digit k) that sum up to num. If it is impossible to form such a set, return -1. The sum of an empty set is 0.

Key Insights

  • A valid number in the set is of the form 10*m + k for some non-negative integer m. (Note: if k is 0, the smallest positive number is 10.)
  • The total sum with n numbers can be expressed as: n*k + 10 * (sum of some non-negative integers).
  • Taking modulo 10 on the equation gives: (n*k) mod 10 must equal (num mod 10).
  • For k ≠ 0, only n in [1, 10] need to be examined because of the periodicity in modulo 10.
  • Special handling is required when num is 0 or k is 0.

Space and Time Complexity

Time Complexity: O(1) - We only check a fixed number of possible n values. Space Complexity: O(1) - Constant amount of extra space is used.

Solution

The solution involves:

  1. Handling the special case where num is 0, returning 0.
  2. Handling the case when k is 0:
    • If num is non-zero and a valid candidate (i.e. ends in 0), we can take num itself if it is a valid positive number with units digit 0; otherwise, return -1.
  3. For k ≠ 0, iterate over possible set sizes n from 1 to 10.
    • For each n, check if nk is not more than num and (num - nk) is divisible by 10.
    • Return the first valid n as the minimum count.
  4. If no valid n is found, return -1.

The algorithm mainly uses a simple loop and modulus arithmetic to determine if a representation is possible.

Code Solutions

# Python solution for Sum of Numbers With Units Digit K
class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        # Special case: the sum zero can be achieved by an empty set
        if num == 0:
            return 0
        
        # If k is 0, the only valid numbers have the form 10*m where m>=1.
        # We can use num itself if num ends with 0 and is at least 10.
        if k == 0:
            if num % 10 == 0:
                return 1  # using [num] as the single number
            else:
                return -1
        
        # For k different from 0, try possible counts from 1 to 10.
        for n in range(1, 11):
            # Check if subtracting the minimal contribution (n*k) gives a remaining sum that's a multiple of 10.
            if num >= n * k and (num - n * k) % 10 == 0:
                return n
        return -1
        
# Example usage:
# sol = Solution()
# print(sol.minimumNumbers(58, 9))  # Output: 2
← Back to All Questions