Decibinary Numbers- Hacker Rank Solution

Decibinary Numbers- Hacker Rank Solution

#include <ios>
#include <iostream>

long long int dp[25][300005] = {};
long long int nm[300005] = {};

long long int cnt(int d, int s)
{
 if (d == -1 && s == 0)
  return 1;
 else if (d == -1)
  return 0;
 else if (dp[d][s] == -1)
 {
  dp[d][s] = 0;
  for (int i = 0; i <= 9 && (1 << d)*i <= s; i++)
   dp[d][s] += cnt(d-1, s-((1 << d)*i));
 }
 return dp[d][s];
}

int main()
{
 std::ios_base::sync_with_stdio(false);
 std::cin.tie(NULL);
 std::cout.tie(NULL);
 for (int i = 0; i < 25; i++)
  for (int j = 0; j < 300005; j++)
   dp[i][j] = -1;
 for (int i = 0; i < 300005; i++)
  nm[i] = cnt(24, i);
 for (int i = 1; i < 300005; i++)
  nm[i] += nm[i-1];
 int q, lo, hi, ans;
 long long int x;

 std::cin >> q;
 while (q--)
 {
  std::cin >> x;
  if (x == 1)
   std::cout << 0 << '\n';
  else
  {
   lo = 0;
   hi = 300004;
   while (lo <= hi)
   {
    int mid = (lo+hi)/2;
    if (nm[mid] >= x)
    {
     ans = mid;
     hi = mid-1;
    }
    else
     lo = mid+1;
   }

   long long int g = x-nm[ans-1];
   long long int s = ans;
   long long int val;
   int d;

   for (int i = -1; cnt(i, s) < g; i++)
    d = i;
   d++;

   while (d >= 0)
   {
    val = 0;
    for (int i = 0; i <= 9; i++)
    {
     if ((s - (1 << d)*i) >= 0)
      val += cnt(d-1, s-(1 << d)*i);
     if (val >= g)
     {
      std::cout << i;
      g -= val-cnt(d-1, s-(1 << d)*i);
      s -= (1 << d)*i;
      break;
     }
    }
    d--;
   }
   std::cout << '\n';
  }
 }
}