Watch 6 video solutions for Find The Least Frequent Digit, a easy level problem involving Array, Hash Table, Math. This walkthrough by Programming Live with Larry has 208 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer n, find the digit that occurs least frequently in its decimal representation. If multiple digits have the same frequency, choose the smallest digit.
Return the chosen digit as an integer.
The frequency of a digit
x is the number of times it appears in the decimal representation of n.
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 <= 231 - 1Problem Overview: You are given a number and need to determine which digit appears the fewest times. The task is essentially a frequency analysis problem: count how often each digit (0–9) occurs and return the digit with the smallest frequency among those present.
Approach 1: Repeated Scan (Brute Force) (Time: O(10n), Space: O(1))
The straightforward way is to check each digit from 0 to 9 and count how many times it appears in the number. For every candidate digit, iterate through the digits of the number and increment a counter whenever a match occurs. Track the smallest count seen so far and update the result accordingly. Since you perform a full scan of the digits up to 10 times, the runtime becomes O(10n), which simplifies to O(n). Space usage stays O(1) because only a few counters are stored.
Approach 2: Counting / Frequency Table (Time: O(n), Space: O(1))
The optimal solution builds a frequency table in a single pass. Iterate through the digits of the number (or its string representation) and increment the count for each digit. A fixed-size array of length 10 works well because digits range from 0 to 9. After building the frequency table, scan the array to find the smallest non‑zero frequency and return the corresponding digit. This approach runs in O(n) time for the initial pass and O(10) for the final scan, which is effectively constant.
This technique is a classic application of counting and hash table style frequency tracking. Because the domain of digits is fixed and small, the memory footprint remains constant at O(1). Many interview problems involving digit statistics or character frequency rely on the same idea.
Implementation details are straightforward. Convert the number to a sequence of digits, update counts while iterating, and then compute the minimum frequency among digits that appear at least once. If multiple digits share the same minimum frequency, returning the smallest digit is a common tie-breaking rule. The algorithm relies only on simple iteration and arithmetic, making it ideal for problems tagged with array and math.
Recommended for interviews: Interviewers expect the frequency counting approach. The brute force scan demonstrates basic reasoning, but building a frequency table in one pass shows that you recognize the pattern of counting occurrences efficiently. This pattern appears frequently in string and digit problems, so mastering it saves time during interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Scan (Brute Force) | O(10n) ≈ O(n) | O(1) | When implementing a quick baseline or demonstrating the basic logic of counting digit occurrences. |
| Frequency Array / Counting | O(n) | O(1) | General case and interview-preferred solution. Single pass counting followed by a constant-time scan of digits 0–9. |