Numbers of length N and value less than K

Given a set of digits (A) in sorted order, find how many numbers of length B are possible whose value is less than number C.

	Input:
	  0 1 5  
	  1  
	  2  
	Output:  
	  2 (0 and 1 are possible)  

	Input:
	  0 1 2 5  
	  2  
	  21  
	Output:
	  5 (10, 11, 12, 15, 20 are possible)

Constraints:

    1 <= B <= 9, 0 <= C <= 1e9 & 0 <= A[i] <= 9

思路:

分三种情况：
B > len(C) => return 0，不可能找到3位数比2位数小
B < len(C) =>
     如果A里面没有0，或者B == 1，return pow(len(A), B)，因为A中的每个数都可以用在B的每一位
     否则，A里面有0，且B > 1，这时候第一位不能用0，所以return (size - 1) * pow(size, B - 1)
B == len(C) =>
     申明两个DP array，一个lower，一个dp。
     lower[i] = 在A中比i小的数有几个
     dp[i] = 用A的前i位能造出比C的前i位的数有几个，我们需要返回的是dp[B]
     dp[1] = lower[C[0]]
        * if (A[0] == 0 && B != 1) dp[1] = lower[C[0]] - 1, 因为第一位不能用0 
     dp[i] = dp[i - 1] * len(A) 
          因为对于dp[i - 1]里的每一个数，我们都能在后面加A中任意的数，使得出来的数小于C[0:i - 1]，
          比如例子中A[0 1 2 5], B = 2, C = 21, dp[1] = 1, 因为0， 1小于2，但是0不能用
          dp[2] = 1 * 4 = 4，因为对于1，我们可以在后面加0，1，2，5任意一个数，得出来的数10，11，12，15肯定小于21
        * 如果C[i - 2] 在A中出现，dp[i] += lower[C[i - 1]]，因为我们还可以用C[0:i - 2] 加上lower[c[i - 1]] 组合出比c[0: i - 1]小的数，
           在上面的例子中，20就是这样的一个数

Solution:

Time: O(B)
Space: O(1)

public class Solution {
    public int solve(ArrayList<Integer> A, int B, int C) {
        int size = A.size();
        if (size == 0) return 0;
        String Cstr = String.valueOf(C);
        int Clength = Cstr.length();
        if (B > Clength) return 0;
        if (B < Clength) {
            if (A.get(0) != 0 || B == 1) {
                return (int) Math.pow(size, B);
            } else {
                return (size - 1) * (int) Math.pow(size, B - 1);
            }
        }
        if (B == Clength) {
            int[] lower = new int[11];
            for (int i = 0; i < size; i ++) {
                lower[A.get(i) + 1] ++;
            }
            for (int i = 1; i <= 10; i ++) {
                lower[i] += lower[i - 1];
            }
            int[] dp = new int[B + 1];
            boolean addLower = true;
            Set<Integer> set = new HashSet<>(A);
            for (int i = 1; i <= B; i ++) {
                int c = Cstr.charAt(i - 1) - '0';
                dp[i] = dp[i - 1] * size;
                if (addLower) {
                    dp[i] += lower[c];
                    addLower = set.contains(c);
                }
                if (i == 1 && B != 1 && A.get(0) == 0) {
                    dp[i] -= 1;
                }
            }
            return dp[B];
        }
        return 0;
    }
}