Skip to main content

273. Integer to English Words

hard

Convert a non-negative integer to its English-word representation. The recursion is structural — chunk into groups of three digits, recurse on each chunk, then append the right scale word.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Convert a non-negative integer num to its English words representation.

Constraints

  • 0 <= num <= 2^31 - 1

Examples

Example 1

Input
num = 123
Output
"One Hundred Twenty Three"

Example 2

Input
num = 12345
Output
"Twelve Thousand Three Hundred Forty Five"

Example 3

Input
num = 1234567
Output
"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Break the number into groups of three digits from the right. Each group has a scale word: '', 'Thousand', 'Million', 'Billion'.

Hint 2

For each non-zero 3-digit group, recurse on belowThousand(group) and append the scale word.

Hint 3

belowThousand handles 0..999: hundreds digit (if any) + 'Hundred' + belowHundred(remainder).

Hint 4

belowHundred handles 0..99: special-case the teens (10..19); otherwise tens + ones.

Solution approach

Reveal approach

Three nested helpers. belowTwenty maps 1..19 to their word; tens maps the tens digit (2..9) to 'Twenty', 'Thirty', ..., 'Ninety'. belowHundred(n): if n < 20 return belowTwenty[n]; else return tens[n/10] + (n%10 ? ' ' + belowTwenty[n%10] : ''). belowThousand(n): handle hundreds digit, then belowHundred of the remainder, glued with 'Hundred'. Main numberToWords(num): if num == 0 return 'Zero'. Loop over scale = ['', 'Thousand', 'Million', 'Billion']: chunk = num % 1000; if chunk > 0, prepend belowThousand(chunk) + ' ' + scale to the result; num /= 1000. Strip trailing space. The recursion is implicit in nesting the helpers. Time and space are O(log n) — number of digits.

Complexity

Time
O(log n)
Space
O(log n)

Related patterns

  • recursion
  • string-construction

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Microsoft
  • Amazon
  • LinkedIn

More Recursion practice problems

See all Recursion problems →