Find The Least Frequent Digit

Difficulty: Easy | Acceptance: 69.70% | Paid: No Topics: Array, Hash Table, Math, Counting

You are given an integer n. Return the least frequent digit in n. If there are multiple digits with the same least frequency, return the smallest one.

• Examples
• Constraints
• Counting Array (Math)
• String Conversion
• Hash Map

Examples

Example 1

Input:

n = 1553322

Output:

1

Explanation: The least frequent digit in n is 1, which appears only once. All other digits appear twice.

Example 2

Input:

n = 723344511

Output:

2

Explanation: The least frequent digits in n are 7, 2, and 5; each appears only once.

Constraints

- 1 <= n <= 2^31​​​​​​​ - 1

Counting Array (Math)

Intuition Since there are only 10 possible digits (0-9), we can use a fixed-size array of length 10 to count the occurrences of each digit. We then iterate through this array to find the digit with the smallest count. If counts are equal, the smaller digit wins.

Steps

• Initialize an array count of size 10 with all zeros.
• Handle the case where n is 0 by incrementing count[0].
• For n > 0, extract the last digit using n % 10, increment its count, and remove the digit using n /= 10.
• Iterate from 0 to 9. Track the minimum frequency found so far and the corresponding digit. Update the answer whenever a strictly smaller frequency is found.

class Solution:
    def findLeastFrequentDigit(self, n: int) -> int:
        count = [0] * 10
        if n == 0:
            count[0] = 1
        else:
            while n > 0:
                digit = n % 10
                count[digit] += 1
                n //= 10
        
        min_freq = float('inf')
        ans = 0
        for i in range(10):
            if count[i] < min_freq:
                min_freq = count[i]
                ans = i
        return ans

Complexity

• Time: O(log n) — We iterate over the number of digits in n, which is log₁₀(n).
• Space: O(1) — The count array is always of fixed size 10.
• Notes: This is the most efficient approach as it avoids string conversion overhead and uses minimal memory.

String Conversion

Intuition Convert the integer to a string to iterate over each digit easily. This approach leverages built-in language features for string iteration, which can be more readable than modulo arithmetic.

Steps

• Convert n to a string s.
• Initialize a count array of size 10 with zeros.
• Iterate through each character c in s. Convert c to an integer and increment the corresponding index in count.
• Iterate from 0 to 9 to find the smallest index with the minimum frequency value.

class Solution:
    def findLeastFrequentDigit(self, n: int) -> int:
        s = str(n)
        count = [0] * 10
        for char in s:
            count[int(char)] += 1
        
        min_freq = float('inf')
        ans = 0
        for i in range(10):
            if count[i] < min_freq:
                min_freq = count[i]
                ans = i
        return ans

Complexity

• Time: O(log n) — Converting to string and iterating takes time proportional to the number of digits.
• Space: O(log n) — The string representation of n requires extra space proportional to the number of digits.
• Notes: Slightly higher space complexity than the math approach due to string allocation, but offers cleaner syntax.

Hash Map

Intuition Use a hash map (or dictionary) to store the frequency of each digit found in n. This is a generalized approach for counting problems, though slightly overkill for the fixed range 0-9.

Steps

• Initialize an empty map.
• Convert n to a string or use math to extract digits.
• Update the count for each digit in the map.
• Iterate from 0 to 9. For each digit, check the map for its frequency (defaulting to 0 if not present). Track the digit with the minimum frequency.

class Solution:
    def findLeastFrequentDigit(self, n: int) -> int:
        from collections import defaultdict
        freq = defaultdict(int)
        
        if n == 0:
            freq[0] = 1
        else:
            while n > 0:
                freq[n % 10] += 1
                n //= 10
        
        min_freq = float('inf')
        ans = 0
        for i in range(10):
            current = freq.get(i, 0)
            if current < min_freq:
                min_freq = current
                ans = i
        return ans

Complexity

• Time: O(log n) — Iterating over digits and the fixed range 0-9.
• Space: O(1) — The map stores at most 10 entries.
• Notes: While functionally correct, using a hash map for a fixed range of 10 digits is less efficient than a simple array due to hashing overhead.