Tap here to switch tabs
Problem
Submissions

Problem: Find the Number of Copy Arrays

Find the Number of Copy Arrays asks you to count arrays whose values stay within given inclusive bounds while matching original's consecutive differences.

Statement

You are given an array of integers original of length nn and a 22D integer array bounds of length nn, where bounds[i] = [u_i, v_i] represents the inclusive range of values copy[i] can take.

An array copy of length nn is considered a copy array of original if both of the following conditions are satisfied:

  • bounds[i][0] ≤\leq copy[i] ≤\leq bounds[i][1] for every ii where 0≤i<n0 \leq i < n.

  • copy[i] - copy[i - 1] is equal to original[i] - original[i - 1] for every ii where 1≤i<n1 \leq i < n.

Return the total number of possible copy arrays.

Constraints:

  • 2≤n=2 \leq n = original.length ≤105\leq 10^5

  • 1≤1 \leq original[i] ≤109\leq 10^9

  • bounds.length =n= n

  • bounds[i].length =2= 2

  • 1≤1 \leq bounds[i][0] ≤\leq bounds[i][1] ≤109\leq 10^9

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find the Number of Copy Arrays

Find the Number of Copy Arrays asks you to count arrays whose values stay within given inclusive bounds while matching original's consecutive differences.

Statement

You are given an array of integers original of length nn and a 22D integer array bounds of length nn, where bounds[i] = [u_i, v_i] represents the inclusive range of values copy[i] can take.

An array copy of length nn is considered a copy array of original if both of the following conditions are satisfied:

  • bounds[i][0] ≤\leq copy[i] ≤\leq bounds[i][1] for every ii where 0≤i<n0 \leq i < n.

  • copy[i] - copy[i - 1] is equal to original[i] - original[i - 1] for every ii where 1≤i<n1 \leq i < n.

Return the total number of possible copy arrays.

Constraints:

  • 2≤n=2 \leq n = original.length ≤105\leq 10^5

  • 1≤1 \leq original[i] ≤109\leq 10^9

  • bounds.length =n= n

  • bounds[i].length =2= 2

  • 1≤1 \leq bounds[i][0] ≤\leq bounds[i][1] ≤109\leq 10^9