Ignore at your own cost:) I can bet easiest to understand


#1

// RP_21

int Solution::solve(int a)
{
// My logic is same but with little difference in grouping.
// I don’t comment much here because it’s too much to write :frowning:
// but please do use paper work, I’m sure one can easily understand this.

// Grouping Palindrom of length n: 1 _ _ (n - 2) _ _ 1
// We have to put 1(no leading 0s) at the starting so as at end.
// so rest n - 2 bits are on focus. // taking even (n - 2)
// as it must be a palindrom, (n - 2) / 2 first bits and last (n - 2) / 2 bits same.
// so palindroms of length n will be 2 ^ [(n - 2) / 2]
// NOTE: for odd (n - 2), div by 2 truncates it, but that one also contribute.
// E.g., _ _ _ mid bit could be 0 or 1 so it 2's power will be ceil of (n - 2) / 2.
// so for general count is be 2 ^ [ceil((n - 2) / 2)].

// so starting from 1 counts for n length will be 1 1 2 2 4 4 ... (understand pattern)
// so first I have found group and length  - l first. then as per the offset
// set selecetd bits around mid bit. see how code that.

int sum = 1;
long long p = 1;
int l = 0;
while(1)
{
    l++;
    if(sum + p > a) break;
    sum += p;
    
    l++;
    if(sum + p > a) break;
    sum += p;
    
    p <<= 1;
}

int diff = a - sum; 
int bits[l]{};
bits[0] = bits[l - 1] = 1;

int mid = l >> 1;
for(int i = 0; diff && i < mid; i++)
{
    // !(l & 1) is for making two mid bit for even length Verify :)
    bits[mid - i - !(l & 1)] = bits[mid + i] = diff & 1;
    diff >>= 1;
}

long long ans = 0;
p = 1;
for(int i = 0; i < l; i++) 
{
    ans += bits[i] * p;
    p <<= 1;
}

return ans;

}