3581. Count Odd Letters from Number 🔒

Description

You are given an integer n perform the following steps:

Convert each digit of n into its lowercase English word (e.g., 4 → "four", 1 → "one").
Concatenate those words in the original digit order to form a string s.

Return the number of distinct characters in s that appear an odd number of times.

Example 1:

Input: n = 41

Output: 5

Explanation:

41 → "fourone"

Characters with odd frequencies: 'f', 'u', 'r', 'n', 'e'. Thus, the answer is 5.

Example 2:

Input: n = 20

Output: 5

Explanation:

20 → "twozero"

Characters with odd frequencies: 't', 'w', 'z', 'e', 'r'. Thus, the answer is 5.

Constraints:

1 <= n <= 10⁹

Solutions

Solution 1: Simulation + Bit Manipulation

We can convert each number into its corresponding English word, then count the frequency of each letter. Since the number of letters is limited, we can use an integer \(\textit{mask}\) to represent the occurrence of each letter. Specifically, we can map each letter to a binary bit of the integer. If a letter appears an odd number of times, the corresponding binary bit is 1; otherwise, it's 0. Finally, we only need to count the number of bits that are 1 in \(\textit{mask}\), which is the answer.

The time complexity is \(O(\log n)\), where \(n\) is the input integer. And the space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRust

d = {
    0: "zero",
    1: "one",
    2: "two",
    3: "three",
    4: "four",
    5: "five",
    6: "six",
    7: "seven",
    8: "eight",
    9: "nine",
}


class Solution:
    def countOddLetters(self, n: int) -> int:
        mask = 0
        while n:
            x = n % 10
            n //= 10
            for c in d[x]:
                mask ^= 1 << (ord(c) - ord("a"))
        return mask.bit_count()

class Solution {
    private static final Map<Integer, String> d = new HashMap<>();
    static {
        d.put(0, "zero");
        d.put(1, "one");
        d.put(2, "two");
        d.put(3, "three");
        d.put(4, "four");
        d.put(5, "five");
        d.put(6, "six");
        d.put(7, "seven");
        d.put(8, "eight");
        d.put(9, "nine");
    }

    public int countOddLetters(int n) {
        int mask = 0;
        while (n > 0) {
            int x = n % 10;
            n /= 10;
            for (char c : d.get(x).toCharArray()) {
                mask ^= 1 << (c - 'a');
            }
        }
        return Integer.bitCount(mask);
    }
}

class Solution {
public:
    int countOddLetters(int n) {
        static const unordered_map<int, string> d = {
            {0, "zero"},
            {1, "one"},
            {2, "two"},
            {3, "three"},
            {4, "four"},
            {5, "five"},
            {6, "six"},
            {7, "seven"},
            {8, "eight"},
            {9, "nine"}};

        int mask = 0;
        while (n > 0) {
            int x = n % 10;
            n /= 10;
            for (char c : d.at(x)) {
                mask ^= 1 << (c - 'a');
            }
        }
        return __builtin_popcount(mask);
    }
};

func countOddLetters(n int) int {
    d := map[int]string{
        0: "zero",
        1: "one",
        2: "two",
        3: "three",
        4: "four",
        5: "five",
        6: "six",
        7: "seven",
        8: "eight",
        9: "nine",
    }

    mask := 0
    for n > 0 {
        x := n % 10
        n /= 10
        for _, c := range d[x] {
            mask ^= 1 << (c - 'a')
        }
    }

    return bits.OnesCount32(uint32(mask))
}

function countOddLetters(n: number): number {
    const d: Record<number, string> = {
        0: 'zero',
        1: 'one',
        2: 'two',
        3: 'three',
        4: 'four',
        5: 'five',
        6: 'six',
        7: 'seven',
        8: 'eight',
        9: 'nine',
    };

    let mask = 0;
    while (n > 0) {
        const x = n % 10;
        n = Math.floor(n / 10);
        for (const c of d[x]) {
            mask ^= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
        }
    }

    return bitCount(mask);
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

impl Solution {
    pub fn count_odd_letters(mut n: i32) -> i32 {
        use std::collections::HashMap;

        let d: HashMap<i32, &str> = [
            (0, "zero"),
            (1, "one"),
            (2, "two"),
            (3, "three"),
            (4, "four"),
            (5, "five"),
            (6, "six"),
            (7, "seven"),
            (8, "eight"),
            (9, "nine"),
        ]
        .iter()
        .cloned()
        .collect();

        let mut mask: u32 = 0;

        while n > 0 {
            let x = n % 10;
            n /= 10;
            if let Some(word) = d.get(&x) {
                for c in word.chars() {
                    let bit = 1 << (c as u8 - b'a');
                    mask ^= bit as u32;
                }
            }
        }

        mask.count_ones() as i32
    }
}

3581. Count Odd Letters from Number 🔒

Description

Solutions

Solution 1: Simulation + Bit Manipulation

Comments