Find The Least Frequent Digit

Easy Arrays & Hashing Hashing Original on LeetCode

Reported atFlipkart

Find The Least Frequent Digit is a easy arrays & hashing problem solved with the hashing pattern. The best approach, optimal (one-pass digit count), runs in O(L) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (count each digit separately) up.

Problem

Given a positive integer n, look at the digits of its decimal representation and return the digit that appears the fewest times. Only digits that actually occur in n are considered.

If several digits share that lowest count, return the smallest of them.

Examples

Example 1

Input
n = 1553322
Output
1
Why
Digit 1 appears once; 5, 3 and 2 each appear twice.

Example 2

Input
n = 723372
Output
2
Why
7, 2 and 3 all appear twice, so the tie goes to the smallest digit, 2.

Example 3

Input
n = 8
Output
8
Why
Only one digit is present. Digits that do not appear (frequency 0) are never candidates.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (count each digit separately)O(10 · L)O(L)
Optimal (one-pass digit count)O(L)O(1)

1Brute force (count each digit separately)

TimeO(10 · L)Ten full passes over the L ≤ 10 digits.
SpaceO(L)The string copy of n.

Turn n into a string. For each candidate digit 0–9, walk the whole string to count it. Track the smallest positive count, preferring smaller digits on ties.

  1. s = decimal string of n.
  2. For d from 0 to 9: c = number of characters in s equal to d.
  3. If c > 0 and c < best, set best = c and answer = d.
class Solution {
    public int getLeastFrequentDigit(int n) {
        String s = Integer.toString(n);
        int best = Integer.MAX_VALUE, ans = -1;
        for (int d = 0; d <= 9; d++) {
            int c = 0;
            for (int i = 0; i < s.length(); i++)
                if (s.charAt(i) - '0' == d) c++;
            if (c > 0 && c < best) { best = c; ans = d; }
        }
        return ans;
    }
}

2Optimal (one-pass digit count)

TimeO(L)One pass over the L digits plus a fixed scan of 10 counters.
SpaceO(1)A fixed array of 10 counts.

Peel digits off with % 10 and / 10, incrementing a count array of size 10. Then scan digits 0 to 9 once and keep the first one with the smallest non-zero count.

  1. cnt[10] = 0; while n > 0: cnt[n % 10]++, n /= 10.
  2. For d from 0 to 9: if cnt[d] > 0 and cnt[d] < best, update best and answer.
  3. Return the answer.
class Solution {
    public int getLeastFrequentDigit(int n) {
        int[] cnt = new int[10];
        while (n > 0) { cnt[n % 10]++; n /= 10; }
        int best = Integer.MAX_VALUE, ans = -1;
        for (int d = 0; d <= 9; d++)
            if (cnt[d] > 0 && cnt[d] < best) { best = cnt[d]; ans = d; }
        return ans;
    }
}

Edge cases to test

  • Single-digit n
  • All digits identical (e.g. 4444)
  • Ties: pick the smallest digit among those with the lowest count
  • Zeros inside the number (e.g. 1000) count as the digit 0
  • Digits with count 0 must be ignored, not treated as least frequent

Hints

Hint 1

There are only ten possible digits. Count how often each one appears.

Hint 2

Scan digits 0 to 9 in increasing order and keep the first one with the smallest non-zero count; scanning upward handles ties for free.

FAQ

What is the best time complexity for Find The Least Frequent Digit?

Optimal (one-pass digit count) runs in O(L) time and O(1) extra space. One pass over the L digits plus a fixed scan of 10 counters.

Which pattern does Find The Least Frequent Digit use?

It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.

Is there a brute force solution for Find The Least Frequent Digit?

Yes. Brute force (count each digit separately) takes O(10 · L) time and O(L) space. Turn n into a string.

Which edge cases should I test for Find The Least Frequent Digit?

Single-digit n; All digits identical (e.g. 4444); Ties: pick the smallest digit among those with the lowest count; Zeros inside the number (e.g. 1000) count as the digit 0; Digits with count 0 must be ignored, not treated as least frequent.