Rely of N digit numbers with at the very least one digit as Okay

Examples:

Enter: N = 3, Okay = 2
Output: 252
Clarification: 
For one incidence of two – 
In a variety of size 3, the next circumstances are doable:
=>When first digit is 2 and different two digits can have 9 values besides ‘2’. 
Thus 9*9 = 81 mixture are doable.
=> When second digit is 2 and first digit can have 8 values from 1 to 9 besides ‘2’ 
and the third digit can have 9 worth from 0 to 9 besides ‘2’.
Thus 8*9 = 72 legitimate mixture.
=>When third digit is 2 the primary digit can have 8 values from 1 to 9 besides ‘2’ 
and the second digit can have 9 values from 0 to 9 besides ‘2’ thus 8*9 = 72. 
Therefore whole legitimate mixture with one incidence of two = 72 + 72 + 81 = 225.
For 2 incidence of two – 
First and second digit could be 2 and third digit can have 9 values from 0 to 9. 
Second and third digit can have worth 2 and first digit 
can have  8 values from 1 to 9 besides 2. 
First and third digit can have values 2 and second digit 
can have 9 values from 0 to 9 besides 2. 
Therefore whole legitimate mixture with two incidence of two = 9 + 8 + 9 = 26.
For all three digits to be 2 – 
There could be just one mixture.
Therefore whole doable numbers with at the very least one incidence of two =  225 + 26 + 1 = 252.

Enter: N = 9, Okay = 8
Output: 555626232

Method: The issue could be solved primarily based on the next mathematical concept:

Discover the distinction between rely of distinctive N digit numbers doable and rely of all distinctive N digit numbers with no incidence of digit Okay.

Observe the steps talked about under to implement this concept: 

• Discover the rely of all N digits numbers = 9 x 10^N-1, Leftmost place could be any digit from 1-9, different digits can have any worth from between 0 and 9.
• Discover the rely of all N digits quantity with no incidence of Okay = 8 x 9^n-1, Leftmost place could be any digit from 1 to 9 besides Okay and different digits can have any worth between 0 to 9 besides Okay.  
• Complete rely of N digit numbers with at the very least one incidence of Okay 
  = Rely of all N digits numbers –  Rely of all N digit numbers with no incidence of Okay.

Beneath is the implementation of the above strategy:

Time Complexity: O(1).
Auxiliary Area: O(1).