Untitled

mail@pastecode.io avatar
unknown
java
a year ago
1.2 kB
25
Indexable
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();
    }
}