FastPrep
Problem · Dynamic Programming

Count Valid Sequences

● MediumOpenAIOA

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.

Examples
01 · Example 1
n = 4
pairs = [[1, 3]]
return = 8
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).
More OpenAI problems
drafts saved locally
public int countValidSequences(int n, int[][] pairs) {
  // write your code here
}
n4
pairs[[1, 3]]
expected8
sign in to submit