Skip to main content
Talentd

Count Odd Letters from Number - Solution & Explanation

EasyPremiumFree on FleetCodeHash TableStringSimulationCounting8 min read
Practice this problem

Problem Statement

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 <= 109

Approach Overview

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

Solution

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

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation + Counting ArrayO(n)O(1)Best for clarity when first explaining frequency counting
Simulation + Bit ManipulationO(n)O(1)Preferred when tracking odd/even parity efficiently

Video Solution

Count Odd Letters from Number • Owen Wu • 18 views views

Frequently Asked Questions

Is Count Odd Letters from Number easy or hard?
Count Odd Letters from Number is generally classified as an easy problem. The core idea is simple frequency counting, and the optimized solution introduces a common bit manipulation trick for tracking odd and even occurrences.
How to solve Count Odd Letters from Number in O(n)?
Convert the number to a string and iterate through its digits. For each digit, compute a letter index and toggle its bit in an integer mask using XOR. This keeps track of whether the frequency is odd or even. Finally, count the set bits in the mask to get the number of letters with odd frequency.
What is the best approach for Count Odd Letters from Number?
The most efficient approach uses simulation with bit manipulation. Iterate through each digit of the number, map it to a letter index, and toggle the corresponding bit in a bitmask. After processing all digits, count the number of set bits in the mask to determine how many letters appear an odd number of times. This runs in O(n) time and O(1) space.
What data structure is used in Count Odd Letters from Number?
The problem typically uses either a small counting array or a bitmask. The array tracks character frequencies directly, while the bitmask stores parity information using bit manipulation. Both approaches rely on constant-size storage because the alphabet size is fixed.
What is the time complexity of Count Odd Letters from Number?
The optimal solution runs in O(n) time where n is the number of digits in the input number. Each digit is processed once, and the bitmask operations are constant time. Space complexity remains O(1) because the mask stores only a fixed number of bits.
Count Odd Letters from Number Python or Java solution approach?
In Python or Java, convert the number to a string, iterate through each digit, compute a letter index, and toggle the corresponding bit using XOR. After the loop, use a built-in bit count operation to count how many bits are set. The overall complexity is O(n) time and O(1) space.
Is Count Odd Letters from Number asked at Google, Amazon, or Meta?
Problems involving frequency counting, parity tracking, and bitmask toggling appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary in wording, the underlying techniques are commonly tested.

Ready to solve this problem?

Practice Count Odd Letters from Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters