← Create New Paste

Integer to English Words (LeetCode 273): Clean Decomposition Under Pressure

6 views
Convert a non-negative integer up to 2^31 - 1 into English words. 123 becomes "One Hundred Twenty Three", 12345 becomes "Twelve Thousand Three Hundred Forty Five", and 1000010 becomes "One Million Ten". There is no clever algorithm here; the interview is about decomposition, edge cases and clean code. Step 1: Notice the structure English names numbers in groups of three digits: units, thousands, millions, billions. Each group is read the same way ("three hundred forty five") and then followed by its scale word. So the problem reduces to: 1. Write a helper that converts 0 to 999. 2. Split the number into three-digit chunks and attach scale words. Step 2: The lookup tables below_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"] tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"] scales = ["", "Thousand", "Million", "Billion"] Numbers below 20 are irregular, which is why they get their own table. Step 3: The code def number_to_words(num): if num == 0: return "Zero" def three(n): words = [] if n >= 100: words += [below_20[n // 100], "Hundred"] n %= 100 if n >= 20: words.append(tens[n // 10]) n %= 10 if n > 0: words.append(below_20[n]) return words result, i = [], 0 while num > 0: chunk = num % 1000 if chunk: result = three(chunk) + ([scales[i]] if scales[i] else []) + result num //= 1000 i += 1 return " ".join(result) Building a list of words and joining once avoids the classic double-space and trailing-space bugs. Edge cases interviewers check - 0 must return "Zero"; the helper alone returns nothing. - Empty chunks: 1000010 has a zero thousands chunk, so "Thousand" must not appear. - Teens: 15 is "Fifteen", not "Ten Five". - Exact tens: 40 is "Forty", with nothing after it. - The maximum value, 2147483647, exercises every scale. Complexity The number of chunks is constant (at most four), so time and space are O(1) for 32-bit input, or O(log n) in general. Follow-ups - British style with "and" ("one hundred and five"). - Ordinals ("twenty-first"). - Reverse direction: parse English words back into an integer, which tests the same decomposition in reverse. How to present it Explain the three-digit grouping idea first, write the helper, then the loop, and trace 1000010 out loud. Under pressure it is easy to forget the empty-chunk rule; Linkjob AI (https://linkjob.ai) offers real-time help during live technical interviews, quietly surfacing reminders like that while you explain your solution in your own words.
Created Nov 17, 2026 21:01 Expires Nov 17, 2027 21:01