LeetCode 3663 - Find The Least Frequent Digit

LeetCode Problem 3663

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math, Counting

Solution

Problem Understanding

The problem asks us to find the least frequent digit in the decimal representation of a given integer n. In other words, we need to count how many times each digit from 0 to 9 appears in the number, and then return the smallest digit that occurs the fewest times.

The input is a single integer n in the range [1, 2^31 - 1]. This means the number can be up to 10 digits long (since 2^31 - 1 = 2147483647). The output is a single integer representing the least frequent digit. If multiple digits share the same minimal frequency, the smallest one among them must be returned.

Important edge cases include numbers where multiple digits occur only once, numbers with all digits the same, or numbers where 0 appears (since 0 may be a valid digit even if the number does not start with it). The problem guarantees that n is positive, so we do not need to handle negative numbers or zero.

Approaches

The brute-force approach is straightforward: convert the number to a string, iterate over each digit, and count its occurrences using a dictionary or array. Once all counts are recorded, we scan through them to find the minimum frequency and select the smallest digit with that frequency. This works correctly because it explicitly counts all digits, but it is not particularly slow given the constraints since the number has at most 10 digits. However, it is less elegant than using a fixed-size array for counting, which is more space-efficient and avoids hashing overhead.

The optimal approach leverages the fact that digits range only from 0 to 9. We can use an array of size 10 to count each digit’s occurrences. After counting, we iterate over the array to find the digit with the minimum count, choosing the smallest in case of ties. This approach is simple, efficient, and well-suited for small fixed-range counts.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Convert number to string and count using a dictionary, where d is the number of digits
Optimal	O(d)	O(1)	Use a fixed array of size 10 to count digits, then scan for minimum frequency

Algorithm Walkthrough

1. Initialize an array count of size 10 with all elements set to 0. This will store the frequency of each digit from 0 to 9.
2. Convert the integer n to a string to easily iterate over each digit.
3. Iterate over each character ch in the string. Convert it to an integer digit and increment count[digit] by 1. This effectively counts the occurrences of each digit.
4. Initialize two variables: min_freq to infinity and result_digit to 0. These will track the smallest frequency found so far and the corresponding digit.
5. Iterate over digits from 0 to 9. For each digit, check if its count is greater than 0 and less than min_freq. If so, update min_freq and result_digit to this digit. If multiple digits share the same minimum frequency, the smaller digit naturally takes precedence because we iterate in ascending order.
6. Return result_digit as the answer.

Why it works: The algorithm works because it maintains a complete frequency count of all digits and systematically checks all digits in ascending order. This guarantees that the digit with the minimum frequency is selected, and ties are resolved correctly by choosing the smaller digit.

Python Solution

class Solution:
    def getLeastFrequentDigit(self, n: int) -> int:
        count = [0] * 10  # Array to store digit frequencies
        
        for ch in str(n):
            digit = int(ch)
            count[digit] += 1
        
        min_freq = float('inf')
        result_digit = 0
        
        for digit in range(10):
            if 0 < count[digit] < min_freq:
                min_freq = count[digit]
                result_digit = digit
        
        return result_digit

The implementation first sets up a frequency array of size 10. It then converts n to a string to iterate over digits easily, counting each occurrence. After counting, it iterates through the array to find the smallest digit with the lowest frequency. The use of float('inf') ensures that any positive count is less than the initial min_freq, and iterating from 0 to 9 guarantees that ties favor the smaller digit.

Go Solution

func getLeastFrequentDigit(n int) int {
    count := [10]int{}
    
    for n > 0 {
        digit := n % 10
        count[digit]++
        n /= 10
    }
    
    minFreq := int(^uint(0) >> 1) // Maximum int
    resultDigit := 0
    
    for digit := 0; digit <= 9; digit++ {
        if count[digit] > 0 && count[digit] < minFreq {
            minFreq = count[digit]
            resultDigit = digit
        }
    }
    
    return resultDigit
}

In Go, we use an array of size 10 to track digit counts. We extract digits using modulo and division instead of converting to a string. We set minFreq to the maximum integer value to ensure the first valid digit is chosen. Iterating from 0 to 9 ensures the smallest digit is selected in case of ties.

Worked Examples

Example 1: n = 1553322

Digit	Count
1	1
2	2
3	2
5	2

The minimum count is 1 for digit 1. Output: 1.

Example 2: n = 723344511

Digit	Count
1	2
2	1
3	2
4	2
5	1
7	1

Digits with minimum frequency 1 are 2, 5, 7. The smallest is 2. Output: 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	We iterate over each digit once and scan the fixed array of size 10
Space	O(1)	Frequency array is of constant size 10 regardless of input size

Since the number has at most 10 digits (due to constraints), both time and space usage are minimal and efficient.

Test Cases

s = Solution()

# Provided examples
assert s.getLeastFrequentDigit(1553322) == 1  # least frequent is 1
assert s.getLeastFrequentDigit(723344511) == 2  # least frequent digits are 2,5,7 -> smallest is 2

# Single digit
assert s.getLeastFrequentDigit(7) == 7  # only one digit, should return itself

# All digits appear once
assert s.getLeastFrequentDigit(1023456789) == 0  # all digits once, smallest is 0

# All digits the same
assert s.getLeastFrequentDigit(11111) == 1  # only one digit

# Two digits tie
assert s.getLeastFrequentDigit(112233) == 1  # digits 1,2,3 tie, smallest is 1

# Number with zeros in middle
assert s.getLeastFrequentDigit(1002) == 2  # digit counts: 1:1,0:2,2:1 -> least freq smallest is 1

Test	Why
1553322	Standard case with clear least frequent digit
723344511	Multiple digits tie, must choose smallest
7	Single-digit input
1023456789	All digits once, choose smallest 0
11111	All digits the same
112233	Multiple digits tie, smallest chosen
1002	Includes zeros in the middle, check counting logic

Edge Cases

Single-digit numbers can be tricky because the frequency array will mostly be zeros. The algorithm handles this by only considering digits with a positive count.

All digits occur equally is another important case, especially when all digits 0-9 appear once. Iterating from 0 ensures that the smallest digit is returned.

Presence of zero must be handled carefully because zeros may appear in the middle or end of the number. In Python, converting to string naturally includes zeros, while in Go, using modulo ensures zeros are counted properly.