FastPrepFastPrep
Problem Brief

Count Valid Sequences

OA

Given n and a list of pairs of numbers that are forbidden to be in the same sequence, provide the number of possible sub-sequences (of any size) with consecutive numbers from 1 to n. Example: for n=4 and pairs=(1,3) there are 8 valid sequences are (1),(2),(3),(4),(1,2),(2,3),(3,4),(2,3,4) with (1,2,3),(1,2,3,4) being invalid as they contain a forbidden pair.

1Example 1

Input
n = 4, pairs = [[1, 3]]
Output
8
Explanation
The valid sequences are (1),(2),(3),(4),(1,2),(2,3),(3,4),(2,3,4). Sequences (1,2,3) and (1,2,3,4) are invalid as they contain the forbidden pair (1,3).
public int countValidSequences(int n, int[][] pairs) {
  // write your code here
}
Input

n

4

pairs

[[1, 3]]

Output

8

Sign in to submit your solution.