You are not logged in. Please login at www.codechef.com to post your questions!

×

BASE - Editorial

PROBLEM LINK:

Practice

Contest

Author: Kevin Charles Atienza

Tester: Kevin Charles Atienza

Editorialist: Vaibhav Tulsyan

DIFFICULTY:

Easy-Medium

PREREQUISITES:

None

PROBLEM:

Given an integer $N$, find the number of integer bases $B$, such that the base-$B$ representation of $N$ starts with a $1$.

QUICK EXPLANATION:

In base $B$, a number with $(K + 1)$ digits is in the range $[B^K, B^{(K + 1)})$. It starts with the digit $1$ if and only if it is in the range $[B^K, 2.B^K)$. Hence, for a base $B$ containing $(K + 1)$ digits, we need to find the no. of bases satisfying $floor({N/2}^{1/K}) \lt B \le N^{1/K}$. The different lengths of bases we need to check are $log_2(N)$, which is at max $40$.

EXPLANATION:

For $N = 0$, the answer is $0$, as no base $B$ representation of $0$ can start with $1$. For $N = 1$, the answer is "INFINITY", as $1$ written in any base $B$ starts with a $1$.

Naive Approach:

We can iterate over all bases in the range $[2, N]$, find the base-$B$ representation of $N$ and check if it starts with $1$.

Pseudo-code: if N == 0: return 0 if N == 1: return "INFINITY" ans = 0 for base in [2..N]: num = n while num > 1: num /= base digit %= base if digit == 1: ans += 1 return ans

This approach is too slow and would pass only Subtask 1.

Expected Solution:

Let's say that a base in consideration $B$ contains $(K + 1)$ digits. Such a base can represent numbers in range: $[B^K, B^{(K + 1)})$. We want the first digit to be equal to $1$. A number $N$ written in base $B$ starts with $1$ if and only if it is in the range $[B^K, 2.B^K)$. This implies, $floor({N/2}) \lt B^K \le N$, which is equivalent to $floor({N/2}^{1/K}) \lt B \le N^{1/K}$. For each value of $K$, we can now find out the bases $B$ that we require - that is, the values of $B$ satisfying this inequality.

Since the maximum value of $N$ in the given problem is $10^{12}$, the highest length of the base that is possible is at most $40$.

Pseudo-code: if N == 0: return 0 if N == 1: return "INFINITY"

ans = 0 for length in [2..40]: val = f(N, length) - f(N / 2, length) ans += val return ans

function f(N, length): x = int(round(pow(N, 1 / length))) while pow(x, length) < N: x += 1 while pow(x, length) > N: x -= 1 return x

Complexity: $O(T * (40.\alpha))$, where $\alpha$ is the complexity of the $pow(a, b)$ function, where $b$ is a floating point number less than $1$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution can be found here.

Tester's solution can be found here.

Editorialist's solution can be found here.

asked 13 Mar '17, 20:31

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

edited 10 Aug '18, 15:54

admin's gravatar image

0★admin ♦♦
19.7k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,629
×82

question asked: 13 Mar '17, 20:31

question was seen: 158 times

last updated: 10 Aug '18, 15:54