public class Solution {
public String solve(int A) {
// log a to base b can be written as log a to base e / log b to base e -> O(logA)
int k = (int)(Math.log(((A-1)/2) + 1) / Math.log(2));
// sum to k terms in G.P a * ((r^n) - 1) / (r - 1) -> O(logk)
int S = 2 * ((int)Math.pow(2, k) - 1), left = A - S - 1;
// 1st element of length (k + 1) -> O(k)
long firstElement = 0, temp = 1;
k++;
while(k-- > 0){
firstElement += temp;
temp *= 10;
}
// iterate over the binary bits of A-S-1 to add it to the firstElement -> O(log(A-S-1))
/* We go over each bit if it is 1 we add temp to the result
* At each step we multiply temp with 10
*/
temp = 1;
while(left > 0){
if((left & 1) == 1)
firstElement += temp;
left >>= 1;
temp *= 10;
}
// build the complete string by adding the reverse of first half -> O()
String ans = String.valueOf(firstElement);
StringBuilder rev = new StringBuilder(ans);
rev.reverse();
return ans + rev.toString();
}
}