CODEWITHSUNDEEP
algorithmnumbers
brijs
brijs

Reputation: 545

Finding number representation in different bases

I was recently solving a problem when I encountered this one: APAC Round E Q2

Basically the question asks to find the smallest base (>1) in which if the number (input) is written then the number would only consist of 1s. Like 3 if represented in base 2 would become 1 (consisting of only 1s).

Now, I tried to solve this the brute force way trying out all bases from 2 till the number to find such a base. But the constraints required a more efficient one.

Can anyone provide some help on how to approach this?

Upvotes: 4

Views: 190

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

We can solve this in O( (log2 n)^2 ) complexity by recognizing that the highest power attainable in the sequence would correspond with the smallest base, 2, and using the formula for geometric sum:

1 + r + r^2 + r^3 ... + r^(n-1) = (1 - r^n) / (1 - r)

Renaming the variables, we get: 

  n = (1 - base^power) / (1 - base)

Now we only need to check power's from (floor(log2 n) + 1) down to 2, and for each given power, use a binary search for the base. For example:

n = 13:

  p = floor(log2 13) + 1 = 4:

    Binary search for base:

    (1 - 13^4) / (1 - 13) = 2380

    ...

    No match for power = 4. 

    Try power = 3:

    (1 - 13^3) / (1 - 13) = 183

    (1 - 6^3) / (1 - 6) = 43

    (1 - 3^3) / (1 - 3) = 13 # match

For n around 10^18 we may need up to (floor(log2 (10^18)) + 1)^2 = 3600 iterations.

Upvotes: 1

QBrute
QBrute

Reputation: 4534

Here is one suggestion: A number x that can be represented as all 1s in a base b can be written as x = b^n + b^(n-1) + b^(n-2) + ... + b^1 + 1

If you subtract 1 from this number you end up with a number divisble by b: b^n + b^(n-1) + b^(n-2) + ... + b^1 which has the representation 111...110. Dividing by b means shifting it right once so the resulting number is now b^(n-1) + b^(n-2) + ... + b^1 or 111...111 with one digit less than before. Now you can repeat the process until you reach 0.

For example 13 which is 111 in base 3:

13 - 1 = 12 --> 110
12 / 3 = 4  -->  11
 4 - 1 = 3  -->  10
 3 / 3 = 1  -->   1
 1 - 1 = 0  -->   0
Done => 13 can be represented as all 1s in base 3

So in order to check if a given number can be written with all 1s in a base b you can check if that number is divisble by b after subtracting 1. If not you can immediately start with the next base.

This is also pretty brute-forcey but it doesn't do any base conversions, only one subtraction, one divisions and one mod operation per iteration.

Upvotes: 2

Related Questions