Company: Google_19july
Difficulty: medium
Number of sequences Problem Description You are given the following: An integer Z An integer O An integer K Task Determine the number of sequences with total length (Z+O) containing exactly Z zeros and O ones such that the length of the longest non-decreasing subsequence in the sequence is at least K. As the number of sequences can be large, find the answer modulo 10 9 + 7. Note: A non-decreasing subsequence of `a` is a sequence of integers a p1 , a p2 , ..., a pm such that p1 < p2 < ... < pm and a p1 ≤ a p2 ≤ ... ≤ a pm . The length of the subsequence is m. Examples Example 1: Input: (Implied by assumptions) Z = 2, O = 2, K = 3 Output: 4 Explanation: Assumptions: Z = 2 O = 2 K = 3 Approach: There are total of six sequences possible: [0, 0, 1, 1] Length of longest non-decreasing subsequence = 4 [0, 1, 0, 1] Length of longest non-decreasing subsequence = 3 [0, 1, 1, 0] Length of longest non-decreasing subsequence = 3 [1, 0, 0, 1] Length of longest non-decreasing subseq