# HackerRank Decibinary Numbers problem solution

In this HackerRank Decibinary Numbers Interview preparation kit problem you will be given q queries in the form of an integer, x. For each x, find and print the xth decibinary number in the list on a new line.

## Problem solution in Python programming.

```#!/bin/python3

import math
import os
import random
import re
import sys

def log(fmt, *args, **kwds):
if not log.verbose:
return
print(fmt.format(*args, **kwds), file=sys.stderr)
log.verbose = False

def makeTable(dmax):
bits = math.ceil(math.log2(dmax))
table = [[0]*dmax for _ in range(bits)]
for ii in range(10):
table[0][ii] = 1
for bit in range(1, bits):
m2 = 1 << bit
t0 = table[bit]
t1 = table[bit-1]
# Limit line to number of possible values that can be represented with
# the current number of decibits
maxlen = 10**(bit+1)
if maxlen > dmax:
maxlen = dmax
for ii in range(maxlen):
# NB: min() is slower than a conditional
pmax = ii//m2
if pmax > 9:
pmax = 9
# NB: sum() is slower than a for loop
total = 0
for pos in range(ii - pmax*m2, ii + m2, m2):
total += t1[pos]
t0[ii] = total
return table

lookup = makeTable(287000)
agg = lookup[-1][:]
for ii in range(1, len(agg)):
agg[ii] += agg[ii-1]
#print(lookup[-1], file=sys.stderr)
#print(agg, file=sys.stderr)

def decibinaryHelper(num, x):
pos = 0
result = 0
for bit in range(len(lookup)-1, 0, -1):
#log('num={} bits={}', num, bit)
digit = 1 << bit
tl = lookup[bit-1]
for kk in range(0, (num//digit) + 1):
remain = num - kk*digit
#log('d={} r={}', kk*digit, remain)
count = tl[remain]
#log('p={} k={} c={}', pos, kk, count)
if (pos + count) <= x:
pos += count
else:
# Found the correct digit
result = (result * 10) + kk
#log('d={} r={} rem={}', kk, result, remain)
num = remain
break
result = (result * 10) + num
return result

def findNum(x):
start = 1
end = len(agg) - 1
while start != end:
num = (start + end) // 2
if agg[num] == x:
return num
elif agg[num] > x:
end = num
else:
start = num + 1
return start

def decibinaryNumbers(x):
if x == 1:
return 0
if x > agg[-1]:
raise ValueError(x)
# for num in range(1, len(agg)):
#     if agg[num] >= x:
#         break
num = findNum(x)
pos = agg[num-1] + 1
result = decibinaryHelper(num, x-pos)
return result

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

q = int(input())

for q_itr in range(q):
x = int(input())

result = decibinaryNumbers(x)

fptr.write(str(result) + '\n')

fptr.close()```

## Problem solution in Java Programming.

```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);
}
}
}```

### Problem solution in C++ programming.

```#include <bits/stdc++.h>
#define pb push_back
#define sqr(x) (x)*(x)
#define sz(a) int(a.size())
#define reset(a,b) memset(a,b,sizeof(a))
#define oo 1000000007

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

int arr[111],cnt,n;
ll dp[30][20],sum[311111];

ll get(int i, int val){
if(i==0) return arr[i]+val<=9;
if(val>=20) return 0;
if(dp[i][val]!=-1) return dp[i][val];
ll &res = dp[i][val];
res = 0;
val += arr[i];
for(int v=0; v<=val && v<=9; ++v)
res += get(i-1, (val-v)*2);
return res;
}

void convert(int v){
cnt=0;
while(v){
arr[cnt++] = v&1;
v>>=1;
}
}

ll f(int v){
if(v==0) return 1;
convert(v);
reset(dp,-1);
return get(cnt-1, 0);
}

ll trackNum(int v, ll k){
convert(v);
reset(dp,-1);
get(cnt-1, 0);
int val = 0;
for(int i=cnt-1; i>=0; --i){
val += arr[i];
if(i==0){
arr[i] = val;
break;
}
for(int v=0; v<=val && v<=9; ++v){
ll x = get(i-1, (val-v)*2);
if(x < k) k -= x;
else{
arr[i] = v;
val = (val-v)*2;
break;
}
}
}
ll res = 0;
for(int i=cnt-1; i>=0; --i) res=res*10+arr[i];
return res;
}

ll query(ll t){
if(t==1) return 0;
--t;
int pos,l=1,r=n,mid;
while(l<=r){
mid=(l+r)/2;
if(sum[mid]>=t){
pos=mid;
r=mid-1;
}else
l=mid+1;
}
t -= sum[pos-1];
return trackNum(pos, t);
}

int main(){
//    freopen("input.txt","r",stdin);
for(n=1; ; ++n){
sum[n]=sum[n-1];
sum[n]+=f(n);
if(sum[n]>(ll)1e16) break;
}
int q;
ll v;
cin>>q;
while(q--){
cin>>v;
cout<<query(v)<<endl;
}
}```

### Problem solution in C programming.

```#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];
}```

### Problem solution in JavaScript programming.

```'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();
});

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);

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

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

ws.end();
}```