PROBLEM LINK:
Setter: sayan_kashyapi
Tester: mishra_roshan , debrc
Editorialist: ritik0602
DIFFICULTY:
Easy
PREREQUISITES:
modulo operator, log function
PROBLEM:
Given a decimal number N and another number B, find the number of digits in it’s equivalent B base number where B ≥ 2.
EXPLANATION
In order to convert a decimal number to a base B number, we keep on dividing that number with B and store the remainders of the diviions. The final ans is the reverse of the number obtained.
So the number of digits can be obtained by counting the number of divisions by B needed to reduce the number to zero.
Also, when N is negative, we can just get rid of the sign.
A quick Mathematical Formula:
The number of digits in base B representation of a decimal number N can be given as :
floor(log(N)/log(B)) + 1, N > 0
For N = 0, we can set the ans to zero as log(0) is not defined.
TIME COMPLEXITY
Time complexity is O(logN) as we keep dividing the number N with B
SOLUTIONS:
Setter's Solution
C++
//number of digits of an b base number of a decimal number
#include<bits/stdc++.h>
using namespace std;
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("op.out", "w", stdout);
// #endif
// long long int t;
long long int t;
// srand(time(NULL));
cin >> t;
// t = 1;
while (t--)
{
long long int n, b, ans;
cin >> n >> b;
// srand(time(0));
// b = (rand() % 19) + 2;
// n = (rand() % 100000) + 1;
// cout << n << " " << b << endl;
ans = n ? log(abs(n)) / log(b) : 0;
cout << ++ans << endl;
}
return 0;
}
Tester's Solution
Java
import java.util.*;
// Compiler version JDK 11.0.2
class Dcoder
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
long n=sc.nextLong();
long b=sc.nextLong();
long ans=(long)(n!=0?((Math.log(Math.abs(n)))/(Math.log(b))):0);
System.out.println(ans+1); }
}
}
Python
for _ in range(inp()):
n,b=minp()
n=abs(n)
if n==0:
print(1)
continue
count=0
while(n>0):
count+=1
n=n//b
print(count)
Feel free to Share your approach.
Suggestions are welcomed as always had been.