how to find integers over a range which contains different digits

Question

Possible Duplicate:
c++ program to find total numbers of integers containing different digits

Suppose i have a unsigned integer, call it low and one another call it high such that high>low. The problem is to find integers which contains distinct digits over this range. For example, suppose low is 1 and high is 10 then the answer is 10, because all the numbers in this range contains distinct digits. If suppose low is 1 and high is 12, then the answer is 10, because 11 contains same digits.example 123,234,4567 is valid number but 121,2342,4546 is invalid number.I am not looking for a bruteforce algo., if anyone has a better solution then a usual bruteforce approach, please tell..

You mean distinct digits between grouping symbols? Or did you mean 123, 234, and 4567 are valid numberS? — Rollie, Nov 10 '12 at 18:58

score 0 · Accepted Answer · answered Nov 10 '12 at 19:06

I would derive an algorithm to determine the number of such digits from 0-n, then you could simply compute (# of valid numbers 0-high) - (# of valid numbers 0-low). To get the valid numbers 0-n, look at the number of digits in your number: if n has 5 digits for example, every valid 1, 2, 3, and 4 digit number is in your result set. So for say a 4 digit number, you compute all the possible combinations of digits in that 4 digit number: 1234, 1235, 1236...5678, 5789, and 6789. Then count the number of permutations (1234 can also be 1243, 1324, 1342...etc), and multiply (# of permutations) x (# of distinct sequences you derived in the previous step). Then you have your answer for all 4 digit numbers. Do the same for each other set, and come up with something more specific for your last set; if high is 5500, you need valid numbers between 5000-5100. You can apply a similar algorithm, but instead of using all digits 0-9, you instead use 9 distinct digits, omitting the '5'. Note that all numbers can have a 0 in them as well, but not at the beginning, so the algorithm would need to account for that as well.

score 0 · Answer 2 · edited May 23 '17 at 12:04

Simply convert your number to a string and then run over it while checking if the given char has already occured in your string. e.g. :

#include <string>

int main()
{
    std::string s = std::to_string(12345);
    bool occuredCheck[10] = {0}; //automatically fills with zeros. 10 values for the 10 numbers
    bool isValidNumber = true;

    for(int i=s.length()-1; i>=0; ++i)
        if(occuredCheck[s[i] - '0'] ^ true == 0) isValidNumber = false;
}

The if-line set's the array-entry to zero, when a diggit occured twice, see XOR. And isValidNumber lets you know if it actually is a valid number for you. BTW: This example needs C++11 for std::to_string.

Using this algorithm you may detect the first invalid number and then set your range using it.

how to find integers over a range which contains different digits

2 Answers2