{"id":2030,"date":"2020-06-12T11:32:17","date_gmt":"2020-06-12T11:32:17","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2030"},"modified":"2022-03-28T23:57:48","modified_gmt":"2022-03-28T23:57:48","slug":"furious-teacher","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/furious-teacher\/","title":{"rendered":"Furious Teacher"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Back Tracking<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given N<\/code>, count all the numbers with unique digits less than 10n<\/sup>. <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n

Idea is to traverse all the numbers less than 10n<\/sup>, and count the numbers with unique digits.<\/p>\n

\"\"<\/p>\n

Method 1 (Brute-Force):<\/h4>\n

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).<\/p>\n

Method 2 (Backtracking):<\/h4>\n

Above approach checks all the combinations one after one upto 10n<\/sup>. In other words the above approach will iterate upto 10n<\/sup> which is beyond the time limit.<\/p>\n

\n

In this method we will use backtracking to solve the above problem.<\/p>\n<\/blockquote>\n

Backtracking<\/strong> 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.
\nWe will store the count of unique digits for each digit (1-n<\/code>).
\nNow for every digit there are atmost 10 choices (0-9<\/code>). 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.<\/p>\n

Algorithm :<\/h3>\n

Back():<\/h4>\n
    \n
  1. If index == target<\/code>, increment the count.<\/li>\n
  2. else, for every k= 0<\/code> to 9<\/code> :\n
      \n
    • if current digit is not visited, mark it visited and,<\/li>\n
    • call back(target,index+1,n)<\/li>\n
    • mark the current digit unvisited (backtracking step).<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

      Complexity Analysis :<\/h3>\n
      \n

      In the first method we are check all the numbers from 0<\/code> to 10n<\/sup>. So the time complexity is 10n<\/sup>.<\/p>\n<\/blockquote>\n

      Solutions:<\/h3>\n

      \t\t\t\t\t\t