Saturday 15 October 2016

Count Numbers with Unique Digits (LeetCode)

Problem: Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.


class Solution {
public:
    int visit[11], steps;
    int countNumbersWithUniqueDigits(int n) {
        if(n>10) n=10;
        int ret=0;
        for(int i=1;i<=n;i++)
        {
            steps = i;
            ret += backTrack(i);
        }
        return ret+1;
    }
    int backTrack(int stepRemaining)
    {
        if(stepRemaining==0)
            return 1;
        int ret=0;
        for(int i=0;i<10;i++)
            if(stepRemaining==steps && i==0) continue;
            else if(visit[i]==0)
            {
                visit[i]=1;
                ret += backTrack(stepRemaining-1);
                visit[i]=0;
            }
        return ret;
    }
};

No comments:

Post a Comment