Concepts Used

Back Tracking

Difficulty Level

Medium

Problem Statement :

Given N, count all the numbers with unique digits less than 10^n.

See original problem statement here

Solution Approach :

Introduction :

Idea is to traverse all the numbers less than 10^n, and count the numbers with unique digits with the help of online coding classes.

Method 1 (Brute-Force):

In this method, we will traverse all the possible numbers. Mark each digit of the number as visited and when any other digit came up which is visited, discard that number. Increment the number count when all the digits of a number are visited and every digit is visited exactly once (No digits are repeated).

Method 2 (Backtracking):

Above approach checks all the combinations one after one upto 10^n. In other words the above approach will iterate upto 10^n which is beyond the time limit.
In this method we will use backtracking to solve the above problem.

Backtracking is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.
We will store the count of unique digits for each digit (1-n).
Now for every digit there are atmost 10 choices (0-9). Each time we visit a digit we will mark it as visited so that we wont visit any digit more than once. Now storing the count of individual digits and adding all the counts of individual digits we get our final answer.

Algorithm :

Back():

  1. If index == target, increment the count.
  2. else, for every k= 0 to 9 :
    • if current digit is not visited, mark it visited and,
    • call back(target,index+1,n)
    • mark the current digit unvisited (backtracking step).

Complexity Analysis :

In the first method we are check all the numbers from 0 to 10^n. So the time complexity is 10^n.

Solutions:

#include <stdio.h>

    int back(int target, int idx, int* visit) {
        if (idx == target)
            return 1;

        int count = 0;
        for (int i = idx?0:1; i < 10; i++) {
            if (!visit[i]) {
                visit[i] = 1;
                count += back(target, idx+1, visit);
                visit[i] = 0;
            }
        }
        return count;
    }

    int solve(int n) {
        int visit[10] = {0};
        int count = 0;
        for (int i = 0; i <= n; i++)
            count += back(i, 0, visit);
        return count;
    }

    int main()
    {  

        int n;
      scanf("%d",&n);
      printf("%d\n",solve(n));

    return 0;
    }
#include <bits/stdc++.h>
    using namespace std;

    int back(int target, int idx, bool* visit) 
    {
        if (idx == target)
            return 1;

        int count = 0;
        for (int i = (idx==0)?1:0; i < 10; i++) 
        {
            if (!visit[i]) 
            {
                visit[i] = true;
                count += back(target, idx+1, visit);
                visit[i] = false;
            }
        }
        return count;
    }

    int solve(int n) {
        bool visit[10] = {false};
        int count = 0;
        for (int i = 0; i <=n; i++)
            count += back(i, 0, visit);
        return count;
    }

    int main()
    {  

        int n;
      cin>>n;
      cout<<solve(n)<<endl;

    return 0;
    }
import java.util.*;
    import java.io.*;

    public class Main {

        public static int countNumbersWithUniqueDigits(int n) {
            if (n > 10) {
                return countNumbersWithUniqueDigits(10);
            }
            int count = 1; // x == 0
            long max = (long) Math.pow(10, n);

            boolean[] used = new boolean[10];

            for (int i = 1; i < 10; i++) {
                used[i] = true;
                count += search(i, max, used);
                used[i] = false;
            }

            return count;
        }

        private static int search(long prev, long max, boolean[] used) {
            int count = 0;
            if (prev < max) {
                count += 1;
            } else {
                return count;
            }

            for (int i = 0; i < 10; i++) {
                if (!used[i]) {
                    used[i] = true;
                    long cur = 10 * prev + i;
                    count += search(cur, max, used);
                    used[i] = false;
                }
            }

            return count;
        }

        public static void main(String[] args)
        {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(countNumbersWithUniqueDigits(n));
        }
    }
Previous post Check SumTree
Next post M-Coloring Problem

Leave a Reply

Your email address will not be published. Required fields are marked *