Problem Description

You are given an integer n. Your task is to find the digit that appears the least number of times in the decimal representation of n.

The problem asks you to:

1. Count how many times each digit (0-9) appears in the number n
2. Find the digit with the lowest frequency (appears the least number of times)
3. If multiple digits have the same lowest frequency, choose the smallest digit among them
4. Return this chosen digit as an integer

For example:

• If n = 112233, the digit 1 appears 2 times, 2 appears 2 times, and 3 appears 2 times. Since all digits have the same frequency, we return the smallest digit which is 1.
• If n = 1122334, the digit 1 appears 2 times, 2 appears 2 times, 3 appears 2 times, and 4 appears 1 time. The digit 4 has the lowest frequency, so we return 4.

Important Note: The frequency of a digit is defined as the number of times it appears in the decimal representation of n. Only digits that actually appear in n are considered (digits with frequency 0 are not considered).

Intuition

To find the digit with the least frequency, we need to know how often each digit appears in the number. This naturally leads us to think about counting - we can create a frequency counter for all possible digits (0-9).

The straightforward approach is to extract each digit from the number one by one and keep track of how many times we see each digit. We can do this by repeatedly taking the remainder when dividing by 10 (which gives us the last digit) and then dividing by 10 to remove that digit.

Once we have the frequency count for all digits, we need to find the minimum frequency. But there's a catch - we only want to consider digits that actually appear in the number (frequency > 0). Among all digits with the minimum frequency, we want the smallest digit value.

The key insight is that we can scan through our frequency array in order (from digit 0 to 9). This way, when we encounter digits with the same frequency, we naturally pick the smaller one first. We keep track of the minimum frequency seen so far and update our answer whenever we find a digit with a lower frequency.

By using divmod(n, 10) repeatedly, we efficiently extract digits and count them. Then a single pass through the frequency array from 0 to 9 ensures we find the least frequent digit, with ties broken by choosing the smaller digit value.

Solution Approach

We use a counting approach to solve this problem. Here's the step-by-step implementation:

Step 1: Initialize the frequency counter

• Create an array cnt of size 10 to store the frequency of each digit (0-9)
• Initialize all counts to 0

Step 2: Extract and count digits

• While n is not zero:
  • Use divmod(n, 10) to simultaneously get the quotient and remainder
  • The remainder x is the current last digit
  • Increment cnt[x] to count this digit
  • Update n to the quotient to remove the processed digit

Step 3: Find the least frequent digit

• Initialize ans = 0 to store the result digit
• Initialize f = inf (infinity) to track the minimum frequency found so far
• Iterate through the cnt array with index x from 0 to 9:
  • Check if 0 < v < f where v = cnt[x]
  • This condition ensures:
    • The digit actually appears in the number (v > 0)
    • Its frequency is less than the current minimum (v < f)
  • If the condition is met:
    • Update f = v (new minimum frequency)
    • Update ans = x (the digit with minimum frequency)

Step 4: Return the result

• Return ans which contains the digit with the least frequency
• Since we iterate from 0 to 9, if multiple digits have the same minimum frequency, we automatically get the smallest digit

The time complexity is O(log n) for extracting digits plus O(10) for finding the minimum, which simplifies to O(log n). The space complexity is O(1) as we use a fixed-size array of 10 elements.

Example Walkthrough

Let's walk through the solution with n = 1123355:

Step 1: Initialize frequency counter

• Create cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] to track digits 0-9

Step 2: Extract and count digits

Processing n = 1123355:

• 1123355 % 10 = 5, 1123355 // 10 = 112335

  • Extract digit 5, increment cnt[5]
  • cnt = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0]

• 112335 % 10 = 5, 112335 // 10 = 11233

  • Extract digit 5, increment cnt[5]
  • cnt = [0, 0, 0, 0, 0, 2, 0, 0, 0, 0]

• 11233 % 10 = 3, 11233 // 10 = 1123

  • Extract digit 3, increment cnt[3]
  • cnt = [0, 0, 0, 1, 0, 2, 0, 0, 0, 0]

• 1123 % 10 = 3, 1123 // 10 = 112

  • Extract digit 3, increment cnt[3]
  • cnt = [0, 0, 0, 2, 0, 2, 0, 0, 0, 0]

• 112 % 10 = 2, 112 // 10 = 11

  • Extract digit 2, increment cnt[2]
  • cnt = [0, 0, 1, 2, 0, 2, 0, 0, 0, 0]

• 11 % 10 = 1, 11 // 10 = 1

  • Extract digit 1, increment cnt[1]
  • cnt = [0, 1, 1, 2, 0, 2, 0, 0, 0, 0]

• 1 % 10 = 1, 1 // 10 = 0

  • Extract digit 1, increment cnt[1]
  • cnt = [0, 2, 1, 2, 0, 2, 0, 0, 0, 0]
  • n = 0, stop

Final frequency count: cnt = [0, 2, 1, 2, 0, 2, 0, 0, 0, 0]

Step 3: Find least frequent digit

Initialize ans = 0, f = inf

Scan through cnt from index 0 to 9:

• x = 0: cnt[0] = 0, skip (digit doesn't appear)
• x = 1: cnt[1] = 2, since 0 < 2 < inf, update f = 2, ans = 1
• x = 2: cnt[2] = 1, since 0 < 1 < 2, update f = 1, ans = 2
• x = 3: cnt[3] = 2, since 2 ≮ 1, no update
• x = 4: cnt[4] = 0, skip (digit doesn't appear)
• x = 5: cnt[5] = 2, since 2 ≮ 1, no update
• x = 6-9: all have cnt[x] = 0, skip

Step 4: Return result

• Return ans = 2

The digit 2 appears only once in 1123355, making it the least frequent digit.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm iterates through each digit of the number n. The number of digits in n is ⌊log₁₀(n)⌋ + 1, which is O(log n). In each iteration, the operations performed (divmod, array access, and increment) are all O(1). After extracting digits, there's a second loop that iterates through the fixed-size array cnt of length 10, which takes O(10) = O(1) time. Therefore, the overall time complexity is O(log n) + O(1) = O(log n).

Space Complexity: O(1)

The algorithm uses a fixed-size array cnt of length 10 to store the frequency count of each digit (0-9). This requires O(10) = O(1) space. Additionally, the algorithm uses a constant amount of extra variables (ans, f, x, v), which also require O(1) space. Since the space usage doesn't grow with the input size n, the overall space complexity is O(1).

Common Pitfalls

Pitfall 1: Considering digits with zero frequency

The Problem: A common mistake is to consider ALL digits from 0-9, including those that don't appear in the number at all. If we don't properly filter out digits with zero frequency, we might incorrectly return a digit that doesn't exist in the number.

Incorrect Implementation:

def getLeastFrequentDigit(self, n: int) -> int:
    digit_count = [0] * 10
  
    while n > 0:
        n, digit = divmod(n, 10)
        digit_count[digit] += 1
  
    # WRONG: This would return 0 for n=123 since digits 0,4,5,6,7,8,9 all have frequency 0
    min_frequency = min(digit_count)
    return digit_count.index(min_frequency)

The Solution: Always check that the frequency is greater than 0 before considering it as a candidate: if 0 < frequency < min_frequency

Pitfall 2: Not handling the tie-breaking rule correctly

The Problem: When multiple digits have the same minimum frequency, the problem requires returning the smallest digit. If we iterate in the wrong order or use the wrong comparison, we might return a larger digit.

Incorrect Implementation:

def getLeastFrequentDigit(self, n: int) -> int:
    digit_count = [0] * 10
  
    while n > 0:
        n, digit = divmod(n, 10)
        digit_count[digit] += 1
  
    result_digit = 0
    min_frequency = inf
  
    # WRONG: Iterating backwards would give us the largest digit with min frequency
    for digit in range(9, -1, -1):
        if 0 < digit_count[digit] <= min_frequency:  # Using <= instead of <
            min_frequency = digit_count[digit]
            result_digit = digit
  
    return result_digit

The Solution:

• Iterate from 0 to 9 (ascending order)
• Use strict less than (<) instead of less than or equal (<=) to only update when we find a strictly smaller frequency
• This ensures we keep the first (smallest) digit when frequencies are equal

Pitfall 3: Edge case with single digit numbers

The Problem: For single-digit numbers like n = 5, the loop executes only once, and we might forget that this is still a valid case that needs proper handling.

The Solution: The current implementation handles this correctly since:

• Even for n = 5, the while loop executes once
• digit_count[5] becomes 1
• The result correctly returns 5 as it's the only digit with non-zero frequency