Problem Description

You are given an integer n. Your task is to:

1. Convert each digit of n into its corresponding lowercase English word:

   • 0 → "zero"
   • 1 → "one"
   • 2 → "two"
   • 3 → "three"
   • 4 → "four"
   • 5 → "five"
   • 6 → "six"
   • 7 → "seven"
   • 8 → "eight"
   • 9 → "nine"

2. Concatenate these words in the same order as the digits appear in n to form a string s.

3. Count how many distinct characters in s appear an odd number of times.

For example, if n = 123:

• The digits are 1, 2, 3
• Converting to words: "one", "two", "three"
• Concatenated string s = "onetwothree"
• Character frequencies:
  • 'o' appears 2 times (even)
  • 'n' appears 1 time (odd)
  • 'e' appears 3 times (odd)
  • 't' appears 2 times (even)
  • 'w' appears 1 time (odd)
  • 'h' appears 1 time (odd)
  • 'r' appears 1 time (odd)
• Distinct characters with odd frequency: 'n', 'e', 'w', 'h', 'r' = 5 characters

The solution uses bit manipulation to track which characters appear an odd number of times. Each character is mapped to a bit position, and XOR operations toggle the bit whenever the character is encountered. At the end, counting the set bits gives the number of characters with odd frequencies.

Intuition

The key insight is recognizing that we only care about whether each character appears an odd or even number of times, not the exact count. This is a perfect scenario for using XOR operations.

Think about XOR's property: a ^ a = 0 and a ^ 0 = a. If we XOR a bit with itself an even number of times, we get 0. If we XOR it an odd number of times, we get 1. This naturally tracks parity (odd/even status).

Since we're dealing with lowercase English letters (only 26 possible characters), we can use a 32-bit integer as a bitmask where each bit position represents a letter. For example, bit 0 represents 'a', bit 1 represents 'b', and so on.

The algorithm works by:

1. For each digit in n, we get its English word representation
2. For each character in that word, we toggle (XOR) the corresponding bit in our mask
3. After processing all characters, any bit that is 1 in the mask represents a character that appeared an odd number of times

Why does this work? Consider tracking the character 'e':

• First occurrence: bit goes from 0 to 1 (odd count)
• Second occurrence: bit goes from 1 to 0 (even count)
• Third occurrence: bit goes from 0 to 1 (odd count)
• And so on...

The bit position formula 1 << (ord(c) - ord('a')) converts a character to its corresponding bit position. For 'a' this gives bit 0, for 'b' bit 1, etc.

Finally, counting the number of 1s in the bitmask gives us the answer - the number of distinct characters that appear an odd number of times. This approach is elegant because it avoids using a frequency map or counter, achieving O(1) space complexity regardless of the input size.

Solution Approach

The solution uses bit manipulation to efficiently track characters with odd frequencies. Here's the step-by-step implementation:

1. Initialize the dictionary and bitmask:

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

The dictionary maps each digit to its English word. The mask variable is our bitmask initialized to 0, where each bit will represent whether a character appears an odd number of times.

2. Extract digits from right to left:

while n:
    x = n % 10
    n //= 10

We process the number digit by digit using modulo operation (n % 10) to get the rightmost digit, then integer division (n //= 10) to remove it.

3. Process each character in the digit's word:

for c in d[x]:
    mask ^= 1 << (ord(c) - ord("a"))

For each character c in the English word:

• ord(c) - ord("a") calculates the character's position (0 for 'a', 1 for 'b', etc.)
• 1 << position creates a bitmask with only that bit set
• mask ^= ... XORs this with our running mask, toggling the bit for that character

4. Count the set bits:

return mask.bit_count()

The bit_count() method returns the number of 1s in the binary representation of mask, which equals the number of characters appearing an odd number of times.

Example walkthrough with n = 21:

• First iteration: x = 1, word = "one"
  • 'o': toggle bit 14
  • 'n': toggle bit 13
  • 'e': toggle bit 4
• Second iteration: x = 2, word = "two"
  • 't': toggle bit 19
  • 'w': toggle bit 22
  • 'o': toggle bit 14 (again, so it becomes 0)
• Final mask has bits set for: 'n', 'e', 't', 'w' (4 characters with odd frequency)
• Return 4

The time complexity is O(k) where k is the total number of characters in all digit words, and space complexity is O(1) since we only use a fixed-size integer for the bitmask.

Example Walkthrough

Let's walk through the solution with n = 205:

Step 1: Initialize

• mask = 0 (all bits are 0)
• Dictionary maps digits to words

Step 2: Process digit 5 (rightmost)

• x = 205 % 10 = 5
• Word is "five"
• Process each character:
  • 'f': bit position = 5, toggle bit 5 → mask = 100000 (binary)
  • 'i': bit position = 8, toggle bit 8 → mask = 100100000
  • 'v': bit position = 21, toggle bit 21 → mask = 1000000000100100000
  • 'e': bit position = 4, toggle bit 4 → mask = 1000000000100110000
• Update n = 205 // 10 = 20

Step 3: Process digit 0

• x = 20 % 10 = 0
• Word is "zero"
• Process each character:
  • 'z': bit position = 25, toggle bit 25 → new bit set
  • 'e': bit position = 4, toggle bit 4 → bit 4 turns OFF (was ON from "five")
  • 'r': bit position = 17, toggle bit 17 → new bit set
  • 'o': bit position = 14, toggle bit 14 → new bit set
• Update n = 20 // 10 = 2

Step 4: Process digit 2

• x = 2 % 10 = 2
• Word is "two"
• Process each character:
  • 't': bit position = 19, toggle bit 19 → new bit set
  • 'w': bit position = 22, toggle bit 22 → new bit set
  • 'o': bit position = 14, toggle bit 14 → bit 14 turns OFF (was ON from "zero")
• n = 2 // 10 = 0, loop ends

Step 5: Count set bits

• Final mask has bits set at positions: 5('f'), 8('i'), 21('v'), 25('z'), 17('r'), 19('t'), 22('w')
• Characters with odd frequency: 'f', 'i', 'v', 'z', 'r', 't', 'w' = 7 characters

Note how 'e' appeared twice (even) so its bit is 0, and 'o' appeared twice (even) so its bit is 0, while all other characters appeared once (odd) so their bits are 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm iterates through each digit of the input number n. Since a number n has O(log n) digits (specifically ⌊log₁₀ n⌋ + 1 digits), the while loop executes O(log n) times. Within each iteration:

• Extracting a digit using modulo and division operations takes O(1) time
• Looking up the word representation in dictionary d takes O(1) time
• The inner for loop iterates through the characters of the digit's word representation, which has at most 5 characters (for words like "three", "seven", "eight"), so this is O(1) time
• The XOR operation and bit shift are O(1) operations

Therefore, the overall time complexity is O(log n) × O(1) = O(log n).

Space Complexity: O(1)

The algorithm uses:

• A fixed-size dictionary d with 10 entries, which is O(1) space
• A single integer variable mask to store the bit representation, which uses at most 26 bits (one for each letter a-z), so O(1) space
• A few temporary variables (x, c) that use O(1) space

The space usage does not grow with the input size n, so the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Digit Processing Order

A critical pitfall is misunderstanding how the digits are processed when using modulo operations. The code extracts digits from right to left (least significant to most significant), but the problem requires concatenating words in the order digits appear in the original number.

Example of the issue:

• For n = 123, the code processes: 3 → 2 → 1
• This gives us "three" + "two" + "one" = "threetwoone"
• But the problem expects: "one" + "two" + "three" = "onetwothree"

Solution: Convert the number to a string first to preserve the digit order:

def countOddLetters(self, n: int) -> int:
    letter_parity_mask = 0
  
    # Convert to string to process digits in correct order
    for digit_char in str(n):
        digit = int(digit_char)
        word = DIGIT_TO_WORD[digit]
      
        for char in word:
            bit_position = ord(char) - ord("a")
            letter_parity_mask ^= 1 << bit_position
  
    return letter_parity_mask.bit_count()

2. Edge Case: n = 0

When n = 0, the while loop while n > 0: never executes, returning 0 instead of processing the single digit "zero".

Solution: Handle zero as a special case or use string conversion:

def countOddLetters(self, n: int) -> int:
    if n == 0:
        # "zero" has z=1, e=1, r=1, o=1 (4 odd characters)
        return 4
  
    letter_parity_mask = 0
    # Rest of the code...

3. Integer Overflow in Other Languages

While Python handles arbitrary precision integers, implementing this in languages like C++ or Java could cause issues with the bitmask for large inputs, especially if using int instead of long or appropriate bit containers.

Solution for other languages: Use appropriate data types (e.g., unsigned int or std::bitset<26> in C++) to ensure all 26 possible letter positions can be tracked.