Problem Statement : Given a set of digits (0-9), find the number of numbers with length N and less than K. To Solve this problem, we will use Digit DP. Brute force approach to solving this problem is to run a for loop and check for individual numbers. Works on small test cases, but fails on large ones. Now, if we use Digit DP, we can solve this more efficiently. State of our DP will be the ith place digit in the number that we want to form and Tight. Tight represents whether the current digit is equal to the digit we desire or not. Thus (tight == 0) represents that the ith place digit is smaller than the ith place digit of limiting number K. So, for example, Our K = 2345, thus when we are forming 2nd place digit, so we can use all the digits less than 3 available in a set with tight = 0 and can use digit 3 with tight = 1. With tight = 0, we can use any integer after that. Whereas with tight = 1, we have to limit our choices for next position. See th...
The expectation of discrete random variable is given by Σ(Pi*Xi) Where Xi = Value of random variable Pi = Probability of random variable Let us suppose that if we choose ith element as the minimum element, then we have to choose remaining x-1 element out of remaining elements which are greater than i . Number of ways to do this is: C(n-i, x-1) The total number of ways to select x elements out of n is C(n,x) . Thus the probability of event is C(n-i, x-1) / C(n,x) . If it is not possible to select x-1 elements out of remaining elements, then the probability is 0. Check out the implementation: Happy Coding :)