×

SIMPLE

# PREREQUISITES

Brute Force, Simple Math

# PROBLEM

A Delicious number is a number which contains digits uniquely. You have to find the number of Delicious numbers between a given range.

# QUICK EXPLANATION

The number of Delicious numbers in a given range can be found in many ways. We have to ensure that we select a manner which is fast enough. Since, there are as many as 200,000 queries per input file, and only a second to spare on it.

You can brute force to generate all the Delicious numbers. There are only 8,877,690 of them. We will cover the details of this generation in the detailed explanation section.

Once this is complete, the answer can be found by performing a binary search on the list of Delicious numbers to find how many of them fall within the range.

Alternately, you can find the number of Delicious numbers below a number through some simple math. This too is covered in the detailed explanation section below.

If we have the number of Delicious numbers that are below a given number, then the answer can be calculated as

numBelow(R) - numBelow(L-1).

# EXPLANATION

## METHOD 1 - Generate all Delicious Numbers

You will not be able to generate Delicious Numbers in any order and then sort them. This turns out to be too slow for the problem. Sorting the numbers takes almost as much time as generating them, and hence by eliminating the need for the sorting step, we can generate the numbers fast enough.

Let us see how we can generate them, in sorted order.

• D is an array of delicious numbers.
• delicious is a queue to store delicious numbers.
• used is a queue that stores masks which represent the digits that are present in the respective delicious number (in the delicious queue).

Initialize delicious and used as follows

for i = 1 to 9
delicious.enque(i)
used.enque(2i)

The following procedure will pick the smallest delicious number from the queue and ensure that the next batch of delicious numbers are generated. Since delicious numbers are being picked in increasing order, we are assured that when the next delicious number if picked (that is, when the procedure is called again); the delicious numbers which are generated will be larger than the ones that were generated in the previous invocation!

procedure
d = delicious.dequeue()
u = used.dequeue()
D.push(d)
_u = invert(u)
for each set-bit i in _u (in increasing order from 0 to 9)
new_d = d*10 + i
new_u = u | 2i
delicious.enqueue(new_d)
used.enqueue(new_u)

You can see the setter's or the tester's solution for an implementation of this approach.

Once the list of numbers have been generated, we can binary search for the position of L and R in the list, and calculate the answer.

## METHOD 2 - Calculate the number of Delicious Numbers less than N

This calculation would require some pre-calculations to be performed.

Let all-delicious(k) be the number of delicious numbers with at most k digits.

all-delicious(0) = 0
all-delicious(1) = 9
all-delicious(2) = 9 * 9 + all-delicious(1)
all-delicious(3) = 9 * 9 * 8 + all-delicious(2)
...
all-delicious(10) = 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 + all-delicious(9)
all-delicious(k) = all-delicious(k-1), for k > 10
(since a delicious number will never have more than 10 digits!)

Let forced-delicious(k,n) be the number of delicious numbers of n digits that can be constructed using k unique digits.

forced-delicious(k,n) = k! / (n-k)!

Let delicious(T) be the number of delicious numbers less than or equal to T.

The intricasies of delicious(T) are best explained in pseudo-code

1   procedure:delicious(T)
2       let k be the number of digits in T
3       result = all-delicious(k-1)
4       if(k > 10) return result
5       // since we have already counted all the delicious numbers
6       Let b be a bit-mask of digits seen till now
7       b = 0
8       for digit d in T from left to right, at position p (1-based)
9           if b.isset(d) then return result
10          // since we have already counted the delicious numbers which are less
11          for digit i = 0 to 9
12              if b.isunset(i) and i < d
13                  result = result + forced-delicious(10-p,k-p)
14          b.set(d)
15      result = result + 1
16      // since the number must itself be a delicious number
17      return result

The above pseudo-code is not entirely correct. In line-11, we seem to always consider all the digits from 0 to 9. But, if k = 0, then we cannot consider 0 as a choice of digit to start the number. Fixing that bug makes delicious(T) complete.

The answer can be found as delicious(R) - delicious(L-1).

# SETTERS SOLUTION

Can be found here.

# TESTERS SOLUTION

Can be found here.

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

6.7k62119138

+1 for brute force

(12 Nov '12, 18:31)

Is forced-delicious(k,n) = k! / (n-k)! correct? If k > n then (n-k)! would be a factorial of a negative number, if k < n then the answer would be 0 since we need at least n unique digits, finally if k = n the answer would be k! but that doesn't correspond with the real answer. Am I missing out something?

(14 Nov '12, 07:36) 3★

 5 can anyone breakdown this tutorial into a simpler version? not able to get it! answered 13 Nov '12, 15:09 2★big_d 76●1●3 accept rate: 0%
 0 Thank you for your reply @jigsaw004 :) Along with your solution I even found the second solution in the above editorial pretty good and easy! @anton_lunyov 's solution follows that concept link:http://www.codechef.com/viewsolution/1507602 Thank you again for taking your time and posting a reply! answered 14 Nov '12, 15:19 2★big_d 76●1●3 accept rate: 0%
 0 I am unable to understand method 1 which involves the generation of delicious numbers. Could anyone please explain the pseudocode in simple terms or provide a more detailed pseudocode? answered 26 Dec '14, 12:29 2★sandy999 391●1●16●38 accept rate: 10%
 0 My code is working fine on my complier (DevC++) Here is the link: http://www.codechef.com/viewsolution/6187493 But, I am getting a "wrong answer" when I submitted my code answered 09 Feb '15, 22:41 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,684
×1,173
×281
×128
×17

question asked: 12 Nov '12, 18:28

question was seen: 4,432 times

last updated: 09 Feb '15, 22:41