You are given an integer n perform the following steps:
n into its lowercase English word (e.g., 4 → "four", 1 → "one").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 <= 109Problem Overview: You are given a number and need to determine how many letters appear an odd number of times after converting its digits into characters. The task is essentially a counting problem where you track the parity (odd or even frequency) of each derived letter.
Approach 1: Simulation + Counting Array (O(n) time, O(1) space)
The direct way is to simulate the transformation and count frequencies. Convert the number to a string and iterate through each digit. Map each digit to a letter (for example 'a' + digit) and maintain a small frequency array of size 10 or 26. After processing all digits, iterate through the frequency array and count how many characters have an odd frequency (freq[i] % 2 == 1). The algorithm runs in O(n) time where n is the number of digits, while space remains O(1) since the alphabet size is constant. This approach is straightforward and easy to reason about during interviews.
Approach 2: Simulation + Bit Manipulation (O(n) time, O(1) space)
A more elegant approach tracks parity using a bitmask instead of explicit counts. While iterating over each digit, compute the mapped letter index and toggle its bit using mask ^= (1 << index). Each toggle flips the parity: the bit becomes 1 if the letter has appeared an odd number of times and 0 if it becomes even again. After processing the entire number, simply count the number of set bits in the mask to determine how many letters appear an odd number of times. This technique avoids maintaining an array and is a common trick in bit manipulation problems.
The bitmask method still scans all digits once, giving O(n) time complexity, while the mask itself uses constant memory (O(1)). It also demonstrates familiarity with parity tracking and bit toggling patterns frequently seen in hash table or string frequency problems.
Recommended for interviews: Start with the simulation and counting explanation to show you understand the core frequency counting idea. Then present the bit manipulation optimization. Interviewers often prefer the bitmask approach because it reduces space usage and shows comfort with low-level operations and parity tracking patterns.
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 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 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).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation + Counting Array | O(n) | O(1) | Best for clarity when first explaining frequency counting |
| Simulation + Bit Manipulation | O(n) | O(1) | Preferred when tracking odd/even parity efficiently |
Practice Count Odd Letters from Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor