Algorithm · Microsoft · Hard
You are given an integer array requiredSum with n entries. Your task is to count how many integer arrays result, also of length n, meet all of the following rules: The array result never decreases from left to right, i.e. result[i] <= result[i + 1] for each valid index i. For every index i, adding up the decimal digits of result[i] gives exactly requiredSum[i]. Every element lies between 1 and 5000 inclusive: 1 <= result[i] <= 5000. Return the number of distinct arrays that…