Find The Least Frequent Digit - Solution & Explanation

Problem 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.