FastPrep
Problem · Dynamic Programming

Count Valid Sequences

Learn this problem
● MediumOpenAI logoOpenAIOA

Problem statement

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.

Function

countValidSequences(n: int, pairs: int[][]) → int

Examples

Example 1

n = 4pairs = [[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
checking account