HackerEarth Binary numbers problem solution

In this HackerEarth Binary numbers problem solution, You are given a set of binary elements. You have to eliminate the binary numbers that contain 11 as a substring. The resultant sequence will be 1, 10, 100, 101, 1000, and so on. You are required to generate the code to determine the Kth value of the new sequence.

HackerEarth Binary numbers problem solution.

#include<bits/stdc++.h>
using namespace std;
 
long long int arr[50]; 
string CodeGenerator (int N) {
    
    string s="";
    int f=0;
        
    for(int i=39;i>=0;i--){
        if(arr[i] <= N){
            f=1;
            s=s+"1";
            N = N-arr[i];
            continue;
        }
            
        if(f==1)
            s=s+"0";       
    }
        
    return s;
}
 
int main() {
 
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    arr[0]=1;
    arr[1]=2;
    
    for(int i=2;i<40;i++)
    {
        arr[i] = arr[i-1] + arr[i-2]; 
    }
    
    
    int T;
    cin >> T;
    for(int t_i=0; t_i<T; t_i++)
    {
        int N;
        cin >> N;
 
        string out_;
        out_ = CodeGenerator(N);
        cout << out_;
        cout << "\n";
    }
}

Second solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <iomanip>
#include <fstream>
#include <stack>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;
 
#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
const int inf = 1034567891;
const ll LL_INF = 1234567890123456789ll;
#define PI 3.14159265
#define endl '\n'
#define F first
#define S second
#define debug(x) cout << #x << " = " << x << endl;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
 
 
template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
  int x = 1 % mod;
  while(b){
    if(b & 1) x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

vector<int> num;

long long dp[60][2][2][2];

long long fun(int ind, int f, int prev, int sub) {
  if (sub)
    return 0;
  if (ind == num.size()) {
    return 1;
  }
  if (~dp[ind][f][prev][sub]) return dp[ind][f][prev][sub];
  int can = (f == 1 ? 1 : num[ind]);
  long long ans = 0;
  for (int i = 0; i <= can; i++) {
    int nf = f, nsub = sub;
    if (!nf && i < num[ind])
      nf = true;
    if (prev == 1 && i == 1)
      nsub = 1;
    ans += fun(ind + 1, nf, i, nsub);
  }
  return dp[ind][f][prev][sub] = ans;
}

map<long long, int> mp;

long long solve(long long n) {
  if (mp.find(n) != mp.end())
    return mp[n];
  num.clear();
  int tn = n;
  while (n) {
    num.push_back(n % 2);
    n /= 2;
  }
  reverse(all(num));
  memset(dp, -1, sizeof(dp));
  long long ans = fun(0, 0, 0, 0);
  mp[tn] = ans - 1;
  return ans - 1;
}

long long get(long long k) {
  long long low = 1, high = 1e12, mid, ans = -1;
  while (low <= high) {
    mid = low + (high - low) / 2;
    if (solve(mid) >= k) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  assert(ans != -1);
  return ans;
}

long long fib[50];

void pre() {
  fib[0] = 1;
  fib[1] = 2;
  for (int i = 2; i < 50; i++) {
    fib[i] = fib[i - 1] + fib[i - 2]; 
  }
}

long long get1(long long k) {
  long long ans = 0;
  for (int i = 49; i >= 0; i--) {
    if (k >= fib[i]) {
      ans += (1ll << i);
      k -= fib[i];
    }
  }
  return ans;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  pre();
  int test;
  cin >> test;
  assert(test >= 1 && test <= 1e5);
  while (test--) {
    int k;
    cin >> k;
    assert(k >= 1 && k <= 1e8);
    long long ans = get1(k);
    vector<int> vec;
    while (ans) {
      vec.push_back(ans % 2);
      ans /= 2;
    }
    reverse(all(vec));
    for (auto it : vec)
      cout << it;
    cout << endl;
  }

  return 0;
}