Skip to content

3663. Find The Least Frequent Digit

SourceBiweekly Contest 164 Q1DifficultyEasyRating1284

Description

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​​​​​​​ - 1

Solutions

Solution 1: Counting

Thinking

Among the decimal digits of \(n\), we want the least frequent one, breaking ties toward the smaller digit. Ten buckets suffice.

Peel digits with \(\textit{divmod}\), then scan the buckets and keep the positive count that is strictly smaller.

Digits that never occur are ignored. There are \(O(\log n)\) digits.

We use an array \(\textit{cnt}\) to count the frequency of each digit. We iterate through each digit of the number \(n\) and update the \(\textit{cnt}\) array.

Then, we use a variable \(f\) to record the current lowest frequency among the digits, and a variable \(\textit{ans}\) to record the corresponding digit.

Next, we iterate through the \(\textit{cnt}\) array. If \(0 < \textit{cnt}[x] < f\), it means we have found a digit with a lower frequency, so we update \(f = \textit{cnt}[x]\) and \(\textit{ans} = x\).

After the iteration, we return \(\textit{ans}\) as the answer.

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def getLeastFrequentDigit(self, n: int) -> int:
        cnt = [0] * 10
        while n:
            n, x = divmod(n, 10)
            cnt[x] += 1
        ans, f = 0, inf
        for x, v in enumerate(cnt):
            if 0 < v < f:
                f = v
                ans = x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int getLeastFrequentDigit(int n) {
        int[] cnt = new int[10];
        for (; n > 0; n /= 10) {
            ++cnt[n % 10];
        }
        int ans = 0, f = 1 << 30;
        for (int x = 0; x < 10; ++x) {
            if (cnt[x] > 0 && cnt[x] < f) {
                f = cnt[x];
                ans = x;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int getLeastFrequentDigit(int n) {
        int cnt[10]{};
        for (; n > 0; n /= 10) {
            ++cnt[n % 10];
        }
        int ans = 0, f = 1 << 30;
        for (int x = 0; x < 10; ++x) {
            if (cnt[x] > 0 && cnt[x] < f) {
                f = cnt[x];
                ans = x;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func getLeastFrequentDigit(n int) (ans int) {
    cnt := [10]int{}
    for ; n > 0; n /= 10 {
        cnt[n%10]++
    }
    f := 1 << 30
    for x, v := range cnt {
        if v > 0 && v < f {
            f = v
            ans = x
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function getLeastFrequentDigit(n: number): number {
    const cnt: number[] = Array(10).fill(0);
    for (; n; n = (n / 10) | 0) {
        cnt[n % 10]++;
    }
    let [ans, f] = [0, Number.MAX_SAFE_INTEGER];
    for (let x = 0; x < 10; ++x) {
        if (cnt[x] > 0 && cnt[x] < f) {
            f = cnt[x];
            ans = x;
        }
    }
    return ans;
}

Comments