Split a Number Into Deci-Binary Numbers
Updated
Problem statement
A deci-binary number is a positive whole number whose digits are all 0 or 1, such as 1, 10 or 1011.
You are given a positive integer n. Split it into the fewest deci-binary numbers that add up to n. The same number may be used more than once.
Often several splits use the fewest numbers. To make the answer unique, choose the split whose biggest number is as big as possible. If that still leaves a tie, make the second-biggest number as big as possible, and so on.
Return the numbers of that split sorted from smallest to largest. Equal numbers each appear in the list, so the length of the list is how many numbers you used.
Function
splitIntoDeciBinary(n: int) → int[]Examples
Example 1
n = 121return = [10,111]The largest digit of 121 is 2, so at least 2 numbers are needed: a deci-binary number adds at most 1 to the tens place. Two splits use exactly 2 numbers: 10 + 111 and 11 + 110. The first split has the bigger biggest number (111 is more than 110), so the answer is [10, 111].
Example 2
n = 3405return = [1,101,1101,1101,1101]The largest digit is 5, so 5 numbers are needed. The biggest number you can take has a 1 wherever 3405 has a nonzero digit: 1101. Taking it three times leaves 3405 - 3303 = 102. From 102 the biggest number is 101, which leaves 1, and then 1. Sorted from smallest to largest, the answer is [1, 101, 1101, 1101, 1101]. The three equal numbers all appear.
Example 3
n = 1000000return = [1000000]1000000 is already deci-binary, so one number is enough and the answer is [1000000].
Constraints
1 <= n <= 10^9
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Server InvestmentRippling · OARippling interview questions
- Maximum Three-Server Difficulty ScoreVisa · OAVisa interview questions
- Particle Moves to TargetCresta · OACresta interview questions
- Warehouse Allocation (Distribute)Amazon · OA
- Find Maximum Even SumIBM · OAIBM interview questions
- Server InvestmentSnowflake · OASnowflake interview questions
- Calculate ChangePayPay · OAPayPay interview questions
- Delete and Freeze GameRubrik · OARubrik interview questions
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Server Upgrade PlanningWells Fargo · OAWells Fargo interview questions