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("0n");
                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:%lldn",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:%lldn",i,y);
            break;
          }
        }
      else
        ans+=i;
    printf("%llun",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();
});

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