Header Ad

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.


HackerRank Decibinary Numbers problem solution


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

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


Post a Comment

3 Comments

  1. It would have been a lot better if there would've been an explanation

    ReplyDelete
    Replies
    1. am working on it please given some time.

      Delete
    2. did you work on your explanation? post it please.

      Delete