Count all numbers with unique digits in the range [0, 10^n].
Example:
Given n = 2, return 91. (the answer should be all numbers between [0,100] excluding [11,22,33,44,55,66,77,88,99,100])
void dfs(int temp, vector<int> &pool, int ct, vector<int> &res, int &n)
{
if(ct>n) return;
res.push_back(temp);
for(int i=0;i<10;i++)
{
if((temp==0 && ct==0 &&i==0) || pool[i]) continue;
pool[i]=1;
dfs(temp*10+i,pool,ct+1,res,n);
pool[i]=0;
}
}
vector<int> func(int n)
{
vector<int> res;
if(n<1) return res;
vector<int> pool(10,0);
int temp=0;
dfs(0,pool,0,res,n);
return res;
}
I used a stupid vector "pool" to store if the numbers are visted or not.
Tried using unordered_set to store but it occurs error when erase an iterator in a while loop, stackflow says erasing the iterator makes iterator point to set.end(). But we also need to insert it back on, error.
Could any one helps with that set issue?
Please correct me if I am wrong, but this looks like a simple combinatorics problem.
First of all, we only need to consider n <= 9. Because for n >= 10, there has to be a number with repeated digit (Pigeon Hole Principle).
Let f(k) = number of numbers with unique digits if the length of the number is k
f(1) = 10
f(k) = 9 * 9 * 8 * ... (9 - k + 2) [The first factor is 9 because a number cannot start with 0].
So the code might look like this:
long countUnique(int n) {
if (n == 0) return 2;
long count = 10;
for (int i = 2; i <= Math.min(n, 10); i++) {
long num = 9 * 9;
for (int j = 1; j <= i - 2; j++) {
num *= (9 - j);
}
count += num;
}
return count;
}
The time and space complexity is actually O(1).
@diptesh I guess, we can only excludes digits repeating in a number., like 11,22,33,44,100 etc but we have to treat 13,31 or 23,32 as unique digits. In your program, you are missing on that point.
@elmirap Yeah, google like clever candidate, coding can not reflect cleverness properly while math can.
@xidui yes, but we have to know all cs techniques (dp, div concuer and bla bla) , our head are full with these stuff, we are overloaded and at the end they give you the problem with the bot and the circle you can or can't draw around it and the interview output depends on your expectations about the interview, are you ready to throw away all cs stuff and to start thinking. In other companies is vice verse. It seems that all depends on what sort of company you apply.
Also what is definition of "clever"? I think that clever in this case shows the degree you are flexible, adaptive
@sindhuri
I think @diptesh 's code is correct. 9 * 9
covers both 13 and 31, or 23 and 32.
The first 9 means you have 9 choice([1,9]) to be the first digit.
The second 9 means you have 9 choice([0,9] exclude the first).
So 13 is covered when you choose 1 as first and 3 as second. 31 is when you choose 3 as first digit and 1 as second. They are all covered in different branches.
@xidui No I disagree. Coding problems if properly chosen can reveal lots of signal about a candidate. Just observe in Discuss where many people posted their code there, it can really surprise you.
@1337c0d3r I definitely agree with you, that coding problems are more useful for the company.
@1337c0d3r
Yeah. I agree with you. I did not mean that coding can not reveal lots of signal. I just meant if you only want to test whether a candidate is clever or not. A math problem may be more suitable than a coding problem.
@xidui Again I argue for the cleverness property of candidate. Clever in what - math, cs ? I don't want to use this word, it is very ambiguous I talk about level of preparation in Math, CS and so on
@xidui Might as well just ask brainteaser / puzzle questions, which is what Google did in their early days. What end up was they hired bunch of Phd's who can't code (or not willing to) according to an article. Now, these type of questions are banned and never asked again.
@xidui IQ also refelects your level of preparation in different domains . You could be brilliant mathematic, physics, medicin but poor cs physician. Also I believe that person like PHD whose passion is to research and find new methods and make discoveries have no place in commercial world to avoid wasting their talent to make world progessive. They should work in research centers.