Lucky String Jackpot

Kuldeep's and Christie recently got their Ph.D. in Maths. So to celebrate, they both decided to play games with mathematical sequences for their date nights.

The game they are playing today is "Jackpot Palindrome", the objective of the game is to find out the length of the largest palindrome which only contains the digit "4" from a given string.

The reference string for today is the lucky string. The lucky string is the concatenation of all lucky numbers in ascending order. Lucky numbers are those numbers that contain only "4" and/or "5". For example 4, 5, 44, 54,55,444 are lucky numbers while 457, 987 ,154 are not. So the first few digits of the lucky string are "4544455455444445454455...".

Since the lucky string is infinite, Christie gives Kuldeep an integer N and Kuldeep only needs to consider the lucky string up to length N.

Every time Kuldeep answers correctly, he gets a kiss from Christie, obviously, he'd want to maximize the number of kisses he gets, so your task is to help Kuldeep answer correctly every time.

Example:

Input:  n = 4
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

long long fastmod(long long n, long long m)
{
    long long ans = 1;
    if (m == 0)
        return 1;
    while (m > 0)
    {
        if (m & 1)
            ans = ans * n;
        m = m >> 1;
        n = n * n;
    }
    return ans;
}

long long luckyStringJackpot(long long n)
{
    long long s = 1;
    long long i = 1;
    while (i * fastmod(2, i) + s <= n)
    {
        s += i * fastmod(2, i);
        i++;
    }
    if ((n - s) >= 2 * i - 1)
        return 2 * i - 1;
    else
        return n - s + 1;
}
int main()
{
    long long n = 4;

    cout << luckyStringJackpot(n) << "\n";
}