Untitled
unknown
java
a year ago
1.2 kB
25
Indexable
Never
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(); } }