We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Dynamic Programming
  4. Decibinary Numbers
  5. Discussions

Decibinary Numbers

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

Sort 17 Discussions, By:

votes
  • recency
  • votes

Please Login in order to post a comment

  • tdprime 1 year ago+ 4 comments

    I want to provide a hint for people who are still trying to wrap their head around the problem. One advanced book that is on topic is, "Combinatorial Algorithms", by Kreher and Stinson.

    My breakthrough happened when I printed out a few tables. Given a function that converts decibinary to its decimal value, the 1 digit numbers have their obvious decimal values. I recommend printing tables of decibinary numbers in groups of 10, then you will start seeing a pattern.

    In python, this might look like,

    >>> [ db_value(x) for x in range(0,10) ]
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> [ db_value(x) for x in range(10,20) ]
    [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
    >>> [ db_value(x) for x in range(20,30) ]
    [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
    >>> [ db_value(x) for x in range(90,100) ]
    [18, 19, 20, 21, 22, 23, 24, 25, 26, 27]
    >>> [ db_value(x) for x in range(100,110) ]
    [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
    
    22|
    Permalink
    • xl6v8 1 year ago+ 0 comments

      Your observation is brilliant!

      1|
      ParentPermalink
    • superparkourio 1 year ago+ 1 comment

      I'm still confused by this problem. How can we work backwards from this pattern to get all the decibinary values for a particular decimal as well as what decimal we need the decibinary values for?

      6|
      ParentPermalink
      • labels 1 year ago+ 0 comments

        My current 60% solution isn't based on this observation at all, I'm trying to understand it so I can make a 100% solution. I don't know how tdprime uses this at all, so I can only guess.

        Consider this: When iterating through the numbers this way, what do you know about the numbers 0-4 once you have reached 100?

        0|
        ParentPermalink
    • antonioaltamura7 9 months ago+ 0 comments

      just wow... but this implies you have precomputed a map, am I right?

      -3|
      ParentPermalink
    • anandbhanu33 4 months ago+ 0 comments

      range(0,9).. range(10,19).. ... range(90,99)..

      0|
      ParentPermalink
  • posto84 2 years ago+ 0 comments

    Example tests:

    2
    1104
    1963
    

    result:

    11111 (31 in decibinary)
    10406 (38 written in decibinary)
    
    5|
    Permalink
  • craig53 8 months ago+ 0 comments

    C++ solution which is logically the same as the one posted previously but hopefully a little easier to understand.

    const int dmax = 300000;
    const int digits = 10;
    const int powers = 20;
    
    vector<vector<long>> v(dmax, vector<long>(powers));
    vector<long> c(dmax);
    
    // Complete the decibinaryNumbers function below.
    void preCompute() {
      // Compute the number of duplicates for each value, number of digits.
      for (int i = 0; i < dmax; i++) {
        v[i][0] = i < digits;
    
        for (int j = 1; j < powers; j++) {
          // Duplicates is sum of all shorter numbers duplicates for each digit.
          for (int k = 0; k < digits; k++) {
            int value = i - k * (1 << j);
    
            // Exit if using digit creates number larger than target value.
            if (value < 0)
              break;
            v[i][j] += v[value][j - 1];
          }
        }
      }
    
      // Calculate the absolute offset for the first duplicate of each number.
      for (int i = 1; i < dmax; i++) {
        c[i] = v[i - 1][powers - 1] + c[i - 1];
      }
    }
    
    long decibinaryNumbers(long x) {
      long result = 0;
      auto l = upper_bound(c.begin(), c.end(), x - 1) - 1;
      int value = l - c.begin();
      long offset = (x - 1) - *l;
    
      // Find each digit.
      for (int i = powers - 1; i >= 1; i--) {
        int power = 1 << i;
    
        // Find the digit which takes us closest to offset.
        for (int digit = 0; digit < digits; digit++) {
          // Calculate value of remaining digits.
          int v1 = value - digit * power;
    
          // If index is less than duplicates for remainder we have our digit.
          if (offset < v[v1][i - 1]) {
            result += digit;
            value -= power * digit;
            break;
          }
    
          // Subtract number of duplicates for this digit from offset.
          offset -= v[v1][i - 1];
        }
    
        result *= 10;
      }
    
      // Whatever is left must be the last digit.
      result += value;
      // cout << x << ":" << result << ":" << l - c.begin() << endl;
    
      return result;
    }
    
    3|
    Permalink
  • ryan249 3 months ago+ 0 comments

    I tried Java 8 but I am having some problems.

    0|
    Permalink
  • hungerfordj 8 months ago+ 0 comments

    Can anyone help suggest a further optimization for the following solution? (I've implemented it in python; it passes 6/11 tests and times out the rest).

    1) Figure out the number of decibinary numbers corresponding to each decimal number using the following dynamic programming algorithm suggested by xinwzh:

    • where g[dec][dig] gives the number of decibinary numbers equal in value to decimal {dec} with at most {dig} digits, you can get g[dec][dig] from: g[dec][dig - 1] + g[dec - offset][dig - 1] + g[dec - 2 x offset][dig - 1] + g[dec - 3 x offset][dig - 1] + ... + g[0][dig - 1], where offset = 2^(dig - 1).
    • Total number of decibinary numbers equal to a given decimal number is retrieved by: g[dec][length of g[dec] - 1]

    2) Add up the number of decibinary numbers corresponding to each decimal from 0, 1, 2, 3, etc. until the total is greater than the query.

    • The decimal that put it over the list is the decimal corresponding to the queried decibinary.
    • The queried decibinary will be the nth decibinary of that decimal, where n is the difference between the query and the previous total (i.e. all the decibinaries up to but not including the decimal corresponding to the queried decibinary).

    3) Find the queried decibinary by either a) finding the first decibinary and cycling up n times, or b) finding the last and cycling down g[dec][len(gs[dec]) -1] - n times.

    • Find the next highest decibinary corresponding to the same decimal number by incrementing up the digits and looking for the first pair of digits where you can subtract two from the lower digit and add one to the higher digit. i.e., 200 -> 1000, 54 -> 62. However, you also need to go back down the digits and maximize in the other direction: 1900 -/-> 2700, 1900 -> 2188.
    • Find the next lowest decibinary by the same thing, but reversed

    Does anyone see where I might be able to optimize something further?? Is it possible to find the nth decibinary number equal to a given decimal number without cycling through the way I'm doing? (This is the bottleneck.)

    0|
    Permalink
  • smartzdp 11 months ago+ 1 comment

    Anyone passed test case 7 & 8 with python3?

    0|
    Permalink
    • wxy1994812 7 months ago+ 0 comments

      my desktop run until out of memory still cant get the result of "8170199978366048"....

      0|
      ParentPermalink
  • kerem_guventurk2 11 months ago+ 1 comment

    I don't understand how x = 20 is 110.

    x = 11 bidecimal = 5, x = 12 bidecimal = 13, x = 13 bidecimal = 21, x = 14 bidecimal = 101, x = 15 bidecimal = 6, x = 16 bidecimal = 14, x = 17 bidecimal = 22, x = 18 bidecimal = 102, x = 19 bidecimal = 110

    Which one am I missing?

    0|
    Permalink
    • alex_fotland 10 months ago+ 0 comments

      You skipped x=18 bidecimal=30.

      1|
      ParentPermalink
  • kworam3 1 year ago+ 1 comment

    My submission is getting a wrong answer on Test Case 3. My list of decibinary numbers appears to be shorter than the expected, because the decibinary number at index 'x' in my list is smaller than the expected decibinary number. Any feedback would be appreciated:

    public static long decibinaryNumbers(long x)
    {
        long idx = x - 1;
        int n = 0;
        long count = 0;
        while (true)
        {
            List<long> repsForN = generateAllDbReps(n);
            if (idx >= count && idx < count + repsForN.Count)
            {
                return repsForN[(int)(idx - count)];
            }
            count += repsForN.Count;
            n++;
        }
    }
    
    public static List<long> generateAllDbReps(int n)
    {
        List<long> result = new List<long>();
        if (n == 0)
        {
            result.Add(0);
            return result;
        }
    
        int place = (int)Math.Floor(Math.Log(n, 2));
        long dbNum = 0;
        internalGenerateAllDbReps(n, place, dbNum, result);
        return result;
    }
    
    private static void internalGenerateAllDbReps(long n, int place, long dbNum, List<long> result)
    {
        if (n == 0)
        {
            result.Add(dbNum);
            return;
        }
    
        if (place < 0)
        {
            return;
        }
    
        long pp2 = (long)Math.Pow(2, place);
        long maxDigit = n / pp2;
        if (maxDigit > 9)
        {
            return;
        }
    
        long pp10 = (long)Math.Pow(10, place);
        for (int digit = 0; digit <= maxDigit; digit++)
        {
            internalGenerateAllDbReps(n - (digit * pp2), place-1, dbNum + (digit * pp10), result);
        }
    }
    
    0|
    Permalink
    • sesteves 1 year ago+ 1 comment

      Could you kindly explain your code?

      0|
      ParentPermalink
      • kworam3 1 year ago+ 0 comments

        decibinaryNumbers(long x) generates all decibinary reps for n=0,1, 2, etc. It sums the counts of these reps until the xth decibinary number is in the current list, and it returns it.

        the generateAllDbReps() method calculates 'place', the leftmost position that could hold a non-zero digit in the decibinary representation of 'n'.

        internalGenerateAllDbReps tries every possible digit in position 'place' for number 'n'. It recurses to the next lower place by adding the digit to the decibinary number 'dbNum' and subtracting the digit from 'n'.

        0|
        ParentPermalink
  • The_Nerd 2 years ago+ 1 comment

    How is the 20th decibinary number 110? I guess it has to be 7. Am i missing something here?

    0|
    Permalink
    • alphaC137 1 year ago+ 0 comments

      19th is 102, 20th 110

      0|
      ParentPermalink
  • MrKristopher 2 years ago+ 0 comments

    This was an interesting problem, until the end. My solution wasn't fast enough for the last data set. I forfeited points to read the editorial and found that my solution was equivalent to the problem setter's, even more optimized. (I tried both filling up dp at the beginning and also using it for memoization w/ recursion; former was faster in PHP.)

    PHP is just too slow for this one. I got 48/60 with PHP, which is the best for PHP on the leaderboard.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature