HackerRank Decibinary Numbers Problem Solution

HackerRank Decibinary Numbers Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Decibinary Numbers Problem Solution. Let’s talk about binary numbers. We have an n-digit binary number. b. and we denote the digit at index i (zero-indexed from right to left) to be by. We can find the decimal value of b using the following formula:

Now that we’ve discussed both systems, let’s combine decimal and binary numbers in a new system we call decibinary! In this number system, each digit ranges from 0 to 9 (like the decimal number system), but the place value of each digit corresponds to the one in the binary number system. For example, the decibinary number 2016 represents the decimal number 24 because:

This is a major problem because our new number system has no real applications beyond
this challenge!
Consider an infinite list of non-negative decibinary numbers that is sorted according to the
following rules:
The decibinary numbers are sorted in increasing order of the decimal value that they evaluate to.

  • Any two decibinary numbers that evaluate to the same decimal value are ordered by increasing decimal value, meaning the equivalent decibinary values are strictly interpreted and compared as decimal values and the smaller decimal value is ordered first. For example, (2) decibinary and (10) decibinary both evaluate to (2)10. We would order (2) decibinary before (10) decibinary because (2)10 < (10)10- Here is a list of first few decibinary numbers properly ordered:

Function Description

Complete the decibinaryNumbers function in the editor below. For each query, it should return the decibinary number at that one-based index.

decibinaryNumbers has the following parameter(s):

  • x: the index of the decibinary number to return

Input Format

The first line contains an integer, q, the number of queries.
Each of the next q lines contains an integer, x, describing a query.

Output Format

For each query, print a single integer denoting the the  decibinary number in the list. Note that this must be the actual decibinary number and not its decimal value. Use 1-based indexing.

Sample Input 0

5
1
2
3
4
10

Sample Output 0

0
1
2
10
100

Explanation 0

For each , we print the  decibinary number on a new line. See the figure in the problem statement.

Sample Input 1

7
8
23
19
16
26
7
6

Sample Output 1

12
23
102
14
111
4
11

Sample Input 2

10
19
25
6
8
20
10
27
24
30
11

Sample Output 2

102
103
11
12
110
100
8
31
32
5
HackerRank Decibinary Numbers Problem Solution
HackerRank Decibinary Numbers Problem Solution

Decibinary Numbers C Solution

#include <stdio.h>
#include <stdlib.h>
#define MAX 500000
int get_i(long long*a,long long num,int size);
long long med(long long*a,int size);
long long dp[30][MAX],sum[MAX],two[30];
unsigned long long ten[30];

int main(){
  int T,i,j,k;
  long long x,y,z;
  unsigned long long ans;
  for(i=two[0]=ten[0]=1;i<30;i++){
    two[i]=two[i-1]*2;
    ten[i]=ten[i-1]*10;
  }
  for(i=0,dp[0][0]=1;i<MAX;i++)
    for(j=1;j<30;j++)
      for(k=0;k<10;k++)
        if(k*two[j-1]<=i)
          dp[j][i]+=dp[j-1][i-k*two[j-1]];
  for(i=0;i<MAX;i++)
    if(i)
      sum[i]=sum[i-1]+dp[29][i];
    else
      sum[i]=dp[29][i];
  scanf("%d",&T);
  while(T--){
    scanf("%lld",&x);
    i=get_i(sum,x,MAX);
    if(i)
      y=x-sum[i-1];
    else
      y=x;
      //printf("i:%d y:%lld\n",i,y);
    for(j=29,ans=0;j>=0;j--)
      if(j)
        for(k=z=0;k<10;k++){
          z+=dp[j][i-k*two[j]];
          if(z>=y){
            y-=z-dp[j][i-k*two[j]];
            i-=k*two[j];
            ans+=k*ten[j];
      //printf("i:%d y:%lld\n",i,y);
            break;
          }
        }
      else
        ans+=i;
    printf("%llu\n",ans);
  }
  return 0;
}
int get_i(long long*a,long long num,int size){
  if(size==0)
    return 0;
  if(num>med(a,size))
    return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
  else
    return get_i(a,num,(size-1)>>1);
}
long long med(long long*a,int size){
  return a[(size-1)>>1];
}

Decibinary Numbers C++ Solution

//#pragma comment(linker,"/STACK:102400000,102400000")
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<time.h>
#include<stdlib.h>
#include<ctype.h>
#include<list>
#include<unordered_map>
//#include<ext/rope>
#define PB push_back
#define MP make_pair
#define PF push_front
#define lson k<<1
#define rson k<<1|1
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;

const int N = 300005;
const int INF = N;
ll number_of_value[N],sum_of_value[N];
unordered_map<ll,ll> single,sum;

void init(){
    number_of_value[0] = sum_of_value[0] = 1;
    ll mx(0);
    for(int i=1;i<N;i++){
        for(int j=0;j<5;j++) if(i/2-j>=0)
            number_of_value[i]+=number_of_value[i/2-j];
        mx = max(mx,number_of_value[i]);
        sum_of_value[i] = sum_of_value[i-1]+number_of_value[i];
    }
//    printf("max: %lld %lld\n",mx,sum_of_value[N-1]);
//    for(int i=1;i<25;i++) printf("%d %lld  %lld \n",i,number_of_value[i],sum_of_value[i]);
}

ll Single(ll n) {
    if(n<N) return number_of_value[n];
    auto t = single.find(n);
    if(t!=single.end()) return t->second;
    ll res = 0;
    for(int i=0;i<5;i++) res += Single(n/2-i);
    single[n] = res;
    return res;
}

ll Sum(ll n) {
    if(n<N) return sum_of_value[n];
    auto t = sum.find(n);
    if(t!=sum.end()) return t->second;
    ll res = 0;
    for(int i=0;i<5;i++) res += Sum(n/2-i);
    if(n&1) {
        sum[n] = res;
        return res;
    }else {
        for(int i=0;i<5;i++) res -= Single(n/2-i);
        sum[n] = res;
        return res;
    }
}

ll calc(ll n){
    sum.clear(),single.clear();
    return Sum(n);
}

ll BinaryFind(ll x) {
    ll l(0),r(INF);
    ll res(-1);
    while(l<=r) {
        ll mid=(l+r)>>1;
        ll tot = calc(mid);
        if(tot<x) {
            res = mid;
            l = mid+1;
        }else r= mid-1;
    }
    return res;
}

void check(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        ll t;
        scanf("%lld",&t);
        printf("%lld  %lld\n",t,calc(t));
    }
}

ll dp[50][10][10],s[50][10];
int a[50],b[50];

ll dfs(int i,int add){
    if(i==-1) return add==0;
    if(add>9) return 0;
    if(s[i][add] !=-1) return s[i][add];
    s[i][add]=0;
    int up = a[i]+add*2;
    for(int j=0;j<=min(9,up);j++) {
        dp[i][add][j]=dfs(i-1,up-j);
        s[i][add] += dp[i][add][j];
    }
    return s[i][add];
}

int main()
{
#ifdef PKWV
//    freopen("in.in","r",stdin);
#endif // PKWV
    init();
//    check();
    int Q;
    scanf("%d",&Q);
    while(Q--){
        ll x;
        scanf("%lld",&x);
        ll val = BinaryFind(x);
//        printf("%lld==\n",val+1);
        ll tmp = val+1;
        int len=0;
        while(tmp) a[len++]=tmp&1,tmp>>=1;
        if(len==0) a[len++]=0;
        memset(s,-1,sizeof(s));
        dfs(len-1,0);
//        printf("%lld==  %lld==\n\n",s[len-1][0],calc(val+1)-calc(val));
//        for(int i=0;i<len;i++) {
//            for(int j=0;j<5;j++)printf("%lld ",s[i][j]);
//            printf("\n");
//        }
        ll order = x - calc(val);
        int add=0;
        for(int i=len-1;i>=0;i--) {
//            printf("order: %lld\n",order);
            ll tmp =0;
            for(int j=0;j<10;j++) {
//                printf("~~~ %d %d  %lld==  %d\n",add,j,dp[i][add][j],tmp);
                if(tmp+dp[i][add][j]>=order) {
                    b[i]=j;
                    order -= tmp;
                    add = a[i]+2*add-j;
                    break;
                }
                tmp += dp[i][add][j];
            }
        }
        bool not_zero=false;
        for(int i=len-1;i>=0;i--) {
            if(b[i]>0) not_zero=true;
            if(not_zero) printf("%d",b[i]);
        }
        if(!not_zero) printf("0");
        printf("\n");
    }
    return 0;
}

Decibinary Numbers C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'decibinaryNumbers' function below.
     *
     * The function is expected to return a LONG_INTEGER.
     * The function accepts LONG_INTEGER x as parameter.
     */

    public static List<List<long>> db_dp;
    public static List<long> dicho;

    public static int dmax = 290000;
    public static int power_ = 20;


    public static void prepare_dp()
    {
        


        db_dp = new List<List<long>>();
        for (int i = 0; i < dmax; i++)
        {
            db_dp.Add(new List<long>(new long[power_]));
        }




        for (int j = 0; j < power_; j++)
        {
            for(int i = 0; i < dmax; i++)
            {
                if (j==0)
                {
                    if (i <= 9)
                        db_dp[i][j] = 1;
                    else
                        db_dp[i][j] = 0;

                    
                    continue;

                }


                int pow2 = (int)Math.Pow(2, j);
                for(int k = 0; k*pow2<=i && k<=9 ;k++)
                {
                    db_dp[i][j] += db_dp[i - k * pow2][j - 1];
                }



                
            }

            
        }
        dicho = new List<long>(new long[dmax]);


        dicho[0] = db_dp[0][power_ - 1];
        for (int i = 1; i < dmax; i++)
            dicho[i] = dicho[i - 1] + db_dp[i][power_ - 1];

        /*
        for(int j = 0;j<6;j++)
            Console.WriteLine("{0}   {1}   ", j, dicho[j]);
        */



    }



    public static int SimpeBisect_v2(List<long> l, long target)
    {
        int low = 0;
        int high = l.Count - 1;
        while (low != high)
        {
            int mid = (low + high) / 2; // Or a fancy way to avoid int overflow
            if (l[mid] <= target)
            {
                /* This index, and everything below it, must not be the first element
                    * greater than what we're looking for because this element is no greater
                    * than the element.
                    */
                low = mid + 1;
            }
            else
            {
                /* This element is at least as large as the element, so anything after it can't
                    * be the first element that's at least as large.
                    */
                high = mid;
            }
        }


        return high;
    }

    public static long decibinaryNumbers(long x)
    {


        if (x == 1)
            return 0;
        if (x == 2)
            return 1;
        if (x == 3)
            return 2;
        if (x == 4)
            return 10;



        
        int l = SimpeBisect_v2(dicho, x);

        if (dicho[l-1] == x)
            l = l - 1;

        long offset = x  - dicho[l-1];
        int v = l;

        //Console.WriteLine("ll {0} offset {1}  value {2}", l, offset, l);


        long res = 0;

        for (int i = power_-1;i>=1;i--)
        {

            //Console.WriteLine("power  {0}",i);
            int pow_j = (int)Math.Pow(2, i);

            for (int j = 0; j < 10; j++)
            {
                //Console.WriteLine(" test {0}  {1}  {2}",j,pow_j, l - j * pow_j);
                if (l - j * pow_j >= 0)
                //Console.WriteLine("j {0} and i {1} and l {2} and db {3}", j, i, l, db_dp[l - j * pow_j][i - 1]);

                if (l - j * pow_j>=0 && offset <= db_dp[l - j * pow_j][i-1])
                {
                    //Console.WriteLine("got in for j {0} and i {1} and l {2} offset {3}", j, i, l,offset);
                    res += j;
                    l = l - j * pow_j;


                    break;
                }

                


                if (l - j * pow_j >= 0)
                    offset = offset - db_dp[l - j*pow_j][i - 1];



            }


            res = res * 10;

        }

        res += l;


        return res;

        

    }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
        
        Result.prepare_dp();

        int q = Convert.ToInt32(Console.ReadLine().Trim());

        for (int qItr = 0; qItr < q; qItr++)
        {
            long x = Convert.ToInt64(Console.ReadLine().Trim());

            long result = Result.decibinaryNumbers(x);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

Decibinary Numbers Java Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int max = 600000;
        int size = 20;
        
        int[] counter = new int[max];
        long[] fresh = new long[max];
        long[] sum = new long[max];
        long[] finder = new long[max];
        
        int[][] prev = new int[max][size];
        long[][] high = new long[max][size];
        long[][] el = new long[max][size];
        
        sum[0] = 1;
        int u = 1;
        long t = 1;
        
        for(int i = 0; i < 20; i++) {
            int last = Math.min(20 * u, max);
                
            
                
                for(int k = 1; k < 10; k++) {
                    for(int j = 0; j < last; j++) {
                if(sum[j] == 0) {
                    continue;
                }
                        
                    int n = k * u + j;
                    
                    if(n >= max) {
                        break;
                    }
                    
                    int p = counter[n];
                    
                    fresh[n] += sum[j];
                    prev[n][p] = j;
                    //data[n][p] = sum[j];
                    high[n][p] = sum[n] + fresh[n];
                    
                    el[n][p] = (long)k * t;
                    counter[n] = p + 1;
                }
            }
            
            for(int j = 0; j < max; j++) {
                sum[j] += fresh[j];
                fresh[j] = 0;
            }
            
            u *= 2;
            t *= 10;
        }
        
        finder[0] = 1;
        
        for(int i = 1; i < max; i++) {
            finder[i] = finder[i - 1] + sum[i];
        }
        
        int count = sc.nextInt();
        long[] tab;
        StringBuilder builder = new StringBuilder();
        
        for(int q = 0; q < count; q++) {
            long p = sc.nextLong();
            
            if(p == 1) {
                builder.append("0\n");
                continue;
            }
            
            int x = find(finder, 1, max - 1, p);
            int y = 0;
            int k = 0;
            
            long s = sum[x];
            long res = 0;
            p -= finder[x - 1];
            
            while(true) {
                tab = high[x];
                k = counter[x];
                y = find(tab, 0, k - 1, p);
                
                res += el[x][y];
                x = prev[x][y];
                
                if(x == 0) {
                    builder.append(res);
                    builder.append('\n');
                    break;
                }
                
                if(y > 0) {
                    p -= tab[y - 1];
                }
            }
        }
        
        System.out.println(builder.toString());
    }
    
    static int find(long[] tab, int a, int b, long n) {
        if(a == b) {
            return a;
        }
        
        if(b - a == 1) {
            if(n > tab[a]) {
                return b;
            }
            
            return a;
        }
        
        int k = (a + b) / 2;
        
        if(n > tab[k]) {
            return find(tab, k + 1, b, n);
        }
        else {
            return find(tab, a, k, n);
        }
    }
}

Decibinary Numbers JavaScript Solution

'use strict';

const fs = require('fs');
const BigNumber = require('bignumber.js');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}
const N = 285133;
const D = 20;


function createDuplicateArr(N, D) {
    let duplicates = new Array(N);
    for(let i=0; i<N; i++) {
        duplicates[i] = new Array(D);
    }
    for(let i=0; i<N; i++) {
        duplicates[i][0] = i < 10 ? 1 : 0
    }
    for(let i=0; i<N; i++) {
        for(let j=1; j<D; j++) {
            duplicates[i][j] = duplicates[i][j-1];
            let m = 1 << j;
            for(let k=1; k<=9; k++) {
                let remN = i - k*m;
                if(remN >= 0) {
                    duplicates[i][j] += duplicates[remN][j - 1];
                } else {
                    break;
                }
            }
        }
    }
    return duplicates;
}

function calcLessThanCounts(duplicates) {
    let lessThanCounts = new Array(duplicates.length);

    lessThanCounts[0] = BigInt(0);
    for(let i=1; i<duplicates.length; i++) {
        lessThanCounts[i] = lessThanCounts[i - 1] + BigInt(duplicates[i - 1][D - 1]);
    }
    return lessThanCounts;
}

function lowerBound(arr, val) {
    let l = 0;
    let h = arr.length;
    while(l < h) {
        let mid = Math.floor((l + h) / 2);
        if(val > arr[mid]) {
            l = mid + 1;
        } else {
            h = mid;
        }
    }
    return l;
}
function lowerBoundBig(arr, val) {
    let l = 0;
    let h = arr.length;
    while(l < h) {
        let mid = Math.floor((l + h) / 2);
        if(BigInt(arr[mid]) < BigInt(val)) {
            l = mid + 1;
        } else {
            h = mid;
        }
    }
    return l;
}

let duplicates = null;
let lessThanCounts = null;


function decibinaryNumbers(x) {
    if(x === 1) {
        return 0;
    }
    if(!duplicates) {
        duplicates = createDuplicateArr(N, D);
        lessThanCounts = calcLessThanCounts(duplicates);
    }

    let decimal = lowerBoundBig(lessThanCounts, x) - 1;
    let index = x - lessThanCounts[decimal];

    let ans = '';
    let ansDigits = lowerBoundBig(duplicates[decimal], index);

    for(let j = ansDigits; j >= 1; j--) {
        let m = 1 << j;
        for(let k=0; k<=9; k++) {
            let remN = decimal - k*m;
            if(remN < 0 || index <= BigInt(duplicates[remN][j-1])) {
                ans += k;
                decimal = decimal - (k)*m;
                break;
            } else {
                index = index - BigInt(duplicates[decimal - k*m][j-1]);
            }
        }
    }
    ans += decimal;
    return ans;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const q = parseInt(readLine(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const x = BigInt(readLine());
        let result = decibinaryNumbers(x);

        ws.write(result + "\n");
    }

    ws.end();
}

Decibinary Numbers Python Solution

import math
import os
import random
import re
import sys
import bisect
import array
import timeit
from itertools import repeat

def decbinValue(x):
    ans = 0
    p2 = 1
    while x > 0:
        ans += (x % 10) * p2
        p2 *= 2
        x //= 10
    return ans

class Solution:
    def __init__(self):
        self.nrepr = {0: 1, 1: 1, 2: 2, 3: 2}
        self.ndrepr = {(0,0): 1}
        #self.initSimple()
        self.init()
        #self.test()
        # self.speedTest()

    def numRepr(self, n):
        if n in self.nrepr:
            return self.nrepr[n]
        ans = 0
        for i in range(10):
            if n-i >= 0 and (n-i)%2 == 0:
                ans += self.numRepr((n-i)//2)
        self.nrepr[n] = ans
        return ans

    def numFixR(self, n, d):
        if (n,d) in self.ndrepr:
            return self.ndrepr[(n,d)]
        if d == 0 and n > 0:
            return 0
        if n > (2**d - 1) * 9:
            return 0
        ans = 0
        for i in range(10):
            if n-i >= 0 and (n-i)%2 == 0:
                ans += self.numFixR((n-i)//2, d-1)
        self.ndrepr[(n,d)] = ans
        return ans

    def test(self):
        print(10**16)
        print(self.numRepr(100000))
        print(self.numRepr(100))
        start = timeit.default_timer()
        self.decibinaryNumbers(10**16)
        stop = timeit.default_timer()
        self.decibinaryNumbers(10**16)
        stop2 = timeit.default_timer()
        print(self.decibinaryNumbers(10**16))
        print('Time 1st: ', stop - start, '2nd:', stop2 - stop)
        for d in range(1, 35000):
            if str(self.decibinaryNumbersSimple(d)) != self.decibinaryNumbers(d):
                print("Yoop", d, self.decibinaryNumbersSimple(d), self.decibinaryNumbers(d))
                break
        a = array.array('q', [1,10**8,10**15,10**16])
        print(a, a.itemsize)

    def speedTest(self):
        print(10**16)
        print(self.numRepr(100000))
        print(self.numRepr(100))
        start = timeit.default_timer()
        self.decibinaryNumbers(10**16)
        stop = timeit.default_timer()
        self.decibinaryNumbers(10**16)
        stop2 = timeit.default_timer()
        print(self.decibinaryNumbers(10**16))
        print('Time 1st: ', stop - start, '2nd:', stop2 - stop)
        t1 = timeit.default_timer()
        for x in range(10**15, 10**15 + 10000):
            self.decibinaryNumbers(x)
        t2 = timeit.default_timer()
        print('Time many: ', t2 - t1)

    def initSimple(self):
        d = {}
        val = 0
        for n in range(1200111):
            if n%10 == 0:
                val = decbinValue(n)
            else:
                val += 1
            if val not in d:
                d[val] = [n]
            else:
                d[val].append(n)
        self.dbl = []
        ls = []
        for v in range(100):
            self.dbl.extend(sorted(d[v]))
            ll = len(d[v])
            ls.append((ll, self.numRepr(v)))
        print(len(self.dbl))

    def decibinaryNumbersSimple(self, x):
        if x <= len(self.dbl):
            return self.dbl[x-1]
        else:
            return 0

    def init(self):
        # tmst1 = timeit.default_timer()
        self.MAX_VAL = 285113
        # print(self.MAX_VAL, bin(self.MAX_VAL), len(bin(self.MAX_VAL)))
        self.MAX_L = 20
        # tmst2 = timeit.default_timer()
        self.ndra = [list(repeat(0, self.MAX_VAL)) for i in range(self.MAX_L)]
        # self.ndra = [array.array('q', repeat(0, self.MAX_VAL)) for i in range(self.MAX_L)]
        # self.ndra = [memoryview(self.mem[i*8*self.MAX_VAL: (i+1)*8*self.MAX_VAL]).cast('q') for i in range(self.MAX_L)]
        # [array.array('q', repeat(0, self.MAX_VAL)) for i in range(self.MAX_L)]
        for d in range(self.MAX_L):
            self.ndra[d][0] = 1
        # tmst3 = timeit.default_timer()
        max_values = [(2**d - 1) * 9 for d in range(self.MAX_L)]
        for v in range(1, self.MAX_VAL):
            # self.ndra[0][v] = 0 # default is zero
            rr = [(v-i)//2 for i in range(10) if v-i >= 0 and (v-i)%2 == 0]
            slc = slice(min(rr), max(rr) + 1)
            for d in range(1, self.MAX_L):
                if v <= max_values[d]:
                    self.ndra[d][v] = sum(self.ndra[d-1][slc])
        # tmst4 = timeit.default_timer()
        self.ssum = list(repeat(0, self.MAX_VAL))
        self.ssum[0] = self.ndra[-1][0]
        for v in range(1, self.MAX_VAL):
            self.ssum[v] = self.ssum[v-1] + self.ndra[-1][v]
        # print(self.ssum[-1])
        # tmst5 = timeit.default_timer()
        # print('Time whole: ', tmst4 - tmst1)
        # print('Time : ', tmst2 - tmst1)
        # print('Time : ', tmst3 - tmst2)
        # print('Time : ', tmst4 - tmst3)
        # print('Time : ', tmst5 - tmst4)
        # for v in range(1, self.MAX_VAL//1000):
        #     d = 3
        #     if self.ndra[d][v] != self.numFixR(v, d):
        #         print("NOOO", v, self.ndra[d][v], self.numFixR(v, d))
        #         break;

    def numFixArr(self, n, d):
        return self.ndra[d][n]

    def decibinaryNumbers(self, x):
        if x == 1:
            return "0"
        # find decibinary value
        v = bisect.bisect_left(self.ssum, x)
        x = x - self.ssum[v-1]
        # v = 0
        # while self.numRepr(v) < x:
        #     x -= self.numRepr(v)
        #     v += 1
        # if v != newv or x != newx:
        #     print("WWW", x, newx, v, newv)
        #     return 0
        # find lenth of result
        l = 0
        while self.ndra[l][v] < x:
            l += 1
        res = [0] * l
        selected_value = 0
        rv = v
        for pos in range(l):
            dig_left = l-pos-1
            p2 = 2**dig_left
            ndra_dig = self.ndra[dig_left]
            for dig in range(10):
                ndr = ndra_dig[rv]
                if ndr < x:
                    x -= ndr
                else:
                    res[pos] = dig
                    break
                rv -= p2
        return "".join(map(str,res))


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input())
    sol = Solution()
    for q_itr in range(q):
        x = int(input())
        result = sol.decibinaryNumbers(x)
        fptr.write(str(result) + '\n')
    fptr.close()
c C# C++ HackerRank Solutions java javascript python