-
Notifications
You must be signed in to change notification settings - Fork 0
/
Smallest_Base.cpp
49 lines (38 loc) · 1008 Bytes
/
Smallest_Base.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#define ll long long int
int isBase(ll base , ll len , ll target ){
ll sum = 0;;
for(int i = 0 ; i < len ; ++i ){
sum = sum * base + 1 ;
if(sum > target){
return 2;
}
}
if(sum < target)
return 0;
return 1;
}
string Solution::solve(string A) {
ll num = stoll(A);
ll ans = num-1;
ll mx_len = log2(num)+1;
for(int i = mx_len ; i >= 2 ; --i){
ll s = 2 , e = num - 1;
while(s <= e){
ll mid = s + (e-s) / 2 ;
int gotSecret = isBase(mid , i , num);
if(gotSecret == 1){
return to_string(mid);
// cout << "yes :" << mid << " ";
// e = mid-1;
// ans = mid;
}
else if(gotSecret == 2){
// s = mid+1;
e = mid -1;
}
else{
s = mid+1;
}
}
}
}