Polydivisible Pandigital Numbers
Hudson River Trading● MediumFULLTIMEPHONE SCREENProblem statement
A number is polydivisible when, for every i from 1 up to its number of digits, the number made by its first i digits is divisible by i. For example, 102 is polydivisible: 1 is divisible by 1, 10 is divisible by 2, and 102 is divisible by 3.
You are given a string digits of distinct decimal digits. Find every polydivisible number that uses each digit in digits exactly once and no other digits.
- A number with two or more digits cannot start with 0.
- Return the numbers as strings, sorted from smallest to largest.
- If no number works, return an empty list.
Function
findPolydivisibleNumbers(digits: String) → String[]Examples
Example 1
digits = "123"return = ["123","321"]Only 123 and 321 work. 123: 1 is divisible by 1, 12 by 2, and 123 by 3. 321: 3 by 1, 32 by 2, and 321 by 3. The other four orders start with 13, 21, 23 or 31, and none of those is divisible by 2.
Example 2
digits = "210"return = ["102","120","201"]The order of the characters in digits does not matter. 012 and 021 are not allowed because they start with 0. 210 fails because 21 is not divisible by 2. The other three numbers pass every check, for example 102: 1 by 1, 10 by 2, and 102 by 3.
Example 3
digits = "0123456789"return = ["3816547290"]This is the classic puzzle with all ten digits, and it has exactly one answer. The prefixes of 3816547290 are 3, 38, 381, 3816, 38165, 381654, 3816547, 38165472, 381654729 and 3816547290, and each one is divisible by its length: 38 = 2 * 19, 3816 = 4 * 954, 3816547 = 7 * 545221 and 3816547290 = 10 * 381654729.
Example 4
digits = "57"return = []57 and 75 are both odd, so neither two-digit number is divisible by 2. No number works, so the answer is an empty list.
Constraints
1 <= digits.length <= 10digitscontains only the characters'0'to'9', and no character appears more than once.