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