A Base of All Ones

Hard

You get an integer number written as a decimal string. Find the smallest base k ≥ 2 in which number is written using only the digit 1, like 111 or 11111. Return that base as a decimal string as well. Such a base always exists: in base number − 1 the number reads 11.

Example 1

number="57" → '7'

57 = 49 + 7 + 1, so in base 7 it is written as 111.

Example 2

number="31" → '2'

31 = 16 + 8 + 4 + 2 + 1, which is 11111 in binary. No base is smaller than 2.

Example 3

number="10" → '9'

Only base 9 works: 10 = 9 + 1, written 11. Any n ≥ 3 is 11 in base n − 1.

Constraints

number is the decimal form of an integer from 3 to 10¹⁸
number has no leading zeros

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Binary Search

Similar problems

K-th Value in a Times Table Hard Factorials With Exactly K Trailing Zeros Hard N-th Multiple of Either Divisor Hard Prototype Drop Tests Hard Numbers From Working Keys Hard

Input

number="57"

Expected

'7'

Run checks the first 3 tests in your browser. Submit checks all 84 tests on the server, hidden ones included.