Write a program that can display all the possible numbers in between given two numbers, having its digits in ascending order. For Example:- Input: 5000 to 6000 Output: 5678 5679 5689 5789 Input: 90 to 124 Output: 123 124 Brute force approach can make it count to all numbers and check of digits for each one of them. But I want approaches that can skip some numbers and can bring complexity lesser than O(n). Do any such solution(s) exists that can give better approach for this problem?

Reputation: 19

Display all the possible numbers having its digits in ascending order

Write a program that can display all the possible numbers in between given two numbers, having its digits in ascending order.

For Example:-

Input: 5000 to 6000
```
Output: 5678 5679 5689 5789
```
Input: 90 to 124
```
Output: 123 124
```

Brute force approach can make it count to all numbers and check of digits for each one of them. But I want approaches that can skip some numbers and can bring complexity lesser than O(n). Do any such solution(s) exists that can give better approach for this problem?

Upvotes: 0

Answers (5)

chepner

Reputation: 531055

Why the brute force algorithm may be very inefficient.

One efficient way of encoding the input is to provide two numbers: the lower end of the range, a, and the number of values in the range, b-a-1. This can be encoded in O(lg a + lg (b - a)) bits, since the number of bits needed to represent a number in base-2 is roughly equal to the base-2 logarithm of the number. We can simplify this to O(lg b), because intuitively if b - a is small, then a = O(b), and if b - a is large, then b - a = O(b). Either way, the total input size is O(2 lg b) = O(lg b).

Now the brute force algorithm just checks each number from a to b, and outputs the numbers whose digits in base 10 are in increasing order. There are b - a + 1 possible numbers in that range. However, when you represent this in terms of the input size, you find that b - a + 1 = 2^{lg (b - a + 1)} = 2^{O(lg b)} for a large enough interval.

This means that for an input size n = O(lg b), you may need to check in the worst case O(2 ⁿ) values.

A better algorithm

Instead of checking every possible number in the interval, you can simply generate the valid numbers directly. Here's a rough overview of how. A number n can be thought of as a sequence of digits n₁ ... n_k, where k is again roughly log₁₀ n.

For a and a four-digit number b, the iteration would look something like

for w in a1 .. 9:
  for x in w+1 .. 9:
    for y in x+1 .. 9:
      for x in y+1 .. 9:
         m = 1000 * w + 100 * x + 10 * y + w
         if m < a:
            next
         if m > b:
            exit
         output w ++ x ++ y ++ z  (++ is just string concatenation)

where a₁ can be considered 0 if a has fewer digits than b.

For larger numbers, you can imagine just adding more nested for loops. In general, if b has d digits, you need d = O(lg b) loops, each of which iterates at most 10 times. The running time is thus O(10 lg b) = O(lg b) , which is a far better than the O(2^{lg b}) running time you get by checking if every number is sorted or not.

One other detail that I have glossed over, which actually does affect the running time. As written, the algorithm needs to consider the time it takes to generate m. Without going into the details, you could assume that this adds at worst a factor of O(lg b) to the running time, resulting in an O(lg² b) algorithm. However, using a little extra space at the top of each for loop to store partial products would save lots of redundant multiplication, allowing us to preserve the originally stated O(lg b) running time.

Upvotes: 1

zeFrenchy

Reputation: 6591

There is only a very limited number of numbers which can match your definition (with 9 digits max) and these can be generated very fast. But if you really need speed, just cache the tree or the generated list and do a lookup when you need your result.

using System;
using System.Collections.Generic;

namespace so_ascending_digits
{
  class Program
  {
    class Node
    {
        int digit;
        int value;
        List<Node> children;

        public Node(int val = 0, int dig = 0)
        {
            digit = dig;
            value = (val * 10) + digit;
            children = new List<Node>();
            for (int i = digit + 1; i < 10; i++)
            {
                children.Add(new Node(value, i));
            }
        }

        public void Collect(ref List<int> collection, int min = 0, int max = Int16.MaxValue)
        {
            if ((value >= min) && (value <= max)) collection.Add(value);
            foreach (Node n in children) if (value * 10 < max) n.Collect(ref collection, min, max);
        }
    }

    static void Main(string[] args)
    {
        Node root = new Node();
        List<int> numbers = new List<int>();
        root.Collect(ref numbers, 5000, 6000);
        numbers.Sort();
        Console.WriteLine(String.Join("\n", numbers));
    }
  }
}

Upvotes: 1

pentadecagon

Reputation: 4847

I offer a solution in Python. It is efficient as it considers only the relevant numbers. The basic idea is to count upwards, but handle overflow somewhat differently. While we normally set overflowing digits to 0, here we set them to the previous digit +1. Please check the inline comments for further details. You can play with it here: http://ideone.com/ePvVsQ

def ascending( na, nb ):
    assert nb>=na
    # split each number into a list of digits
    a = list( int(x) for x in str(na))
    b = list( int(x) for x in str(nb))

    d = len(b) - len(a)

    # if both numbers have different length add leading zeros 
    if d>0:
        a = [0]*d + a  # add leading zeros
    assert len(a) == len(b)
    n = len(a)


    # check if the initial value has increasing digits as required,
    # and fix if necessary
    for x in range(d+1, n):
        if a[x] <= a[x-1]:
            for y in range(x, n):
                a[y] = a[y-1] + 1
            break

    res = [] # result set

    while a<=b:
        # if we found a value and add it to the result list
        # turn the list of digits back into an integer
        if max(a) < 10:
            res.append( int( ''.join( str(k) for k in a ) ) )

        # in order to increase the number we look for the
        # least significant digit that can be increased
        for x in range( n-1, -1, -1): # count down from n-1 to 0
            if a[x] < 10+x-n:
                break
        # digit x is to be increased
        a[x] += 1
        # all subsequent digits must be increased accordingly
        for y in range( x+1, n ):
            a[y] = a[y-1] + 1

    return res

print( ascending( 5000, 9000 ) )

Upvotes: 2

Mikhail

Reputation: 21749

Sounds like task from Project Euler. Here is the solution in C++. It is not short, but it is straightforward and effective. Oh, and hey, it uses backtracking.

// Higher order digits at the back
typedef std::vector<int> Digits;

// Extract decimal digits of a number
Digits ExtractDigits(int n)
{
  Digits digits;

  while (n > 0)
  {
    digits.push_back(n % 10);
    n /= 10;
  }

  if (digits.empty())
  {
    digits.push_back(0);
  }

  return digits;
}

// Main function
void PrintNumsRec(
  const Digits& minDigits,  // digits of the min value
  const Digits& maxDigits,  // digits of the max value
  Digits& digits,  // digits of current value
  int pos,         // current digits with index greater than pos are already filled
  bool minEq,      // currently filled digits are the same as of min value
  bool maxEq)      // currently filled digits are the same as of max value
{
  if (pos < 0)
  {
    // Print current value. Handle leading zeros by yourself, if need
    for (auto pDigit = digits.rbegin(); pDigit != digits.rend(); ++pDigit)
    {
      if (*pDigit >= 0)
      {
        std::cout << *pDigit;
      }
    }
    std::cout << std::endl;
    return;
  }

  // Compute iteration boundaries for current position
  int first = minEq ? minDigits[pos] : 0;
  int last = maxEq ? maxDigits[pos] : 9;

  // The last filled digit
  int prev = digits[pos + 1];

  // Make sure generated number has increasing digits
  int firstInc = std::max(first, prev + 1);

  // Iterate through possible cases for current digit
  for (int d = firstInc; d <= last; ++d)
  {
    digits[pos] = d;

    if (d == 0 && prev == -1)
    {
      // Mark leading zeros with -1
      digits[pos] = -1;
    }

    PrintNumsRec(minDigits, maxDigits, digits, pos - 1, minEq && (d == first), maxEq && (d == last));
  }
}

// High-level function
void PrintNums(int min, int max)
{
  auto minDigits = ExtractDigits(min);
  auto maxDigits = ExtractDigits(max);

  // Make digits array of the same size
  while (minDigits.size() < maxDigits.size())
  {
    minDigits.push_back(0);
  }

  Digits digits(minDigits.size());

  int pos = digits.size() - 1;

  // Placeholder for leading zero
  digits.push_back(-1);

  PrintNumsRec(minDigits, maxDigits, digits, pos, true, true);
}

void main()
{
  PrintNums(53, 297);
}

It uses recursion to handle arbitrary amount of digits, but it is essentially the same as the nested loops approach. Here is the output for (53, 297):

Much more interesting problem would be to count all these numbers without explicitly computing it. One would use dynamic programming for that.

Upvotes: 1

500 - Internal Server Error

Reputation: 28829

One way (pseudo-code):

for (digit3 = '5'; digit3 <= '6'; digit3++)
  for (digit2 = digit3+1; digit2 <= '9'; digit2++)
    for (digit1 = digit2+1; digit1 <= '9'; digit1++)
      for (digit0 = digit1+1; digit0 <= '9'; digit0++)
        output = digit3 + digit2 + digit1 + digit0; // concatenation

Upvotes: 0

Display all the possible numbers having its digits in ascending order

Answers (5)

Why the brute force algorithm may be very inefficient.

A better algorithm

Related Questions