Arithmetic Subsequences

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, …, Pk) such that 0 ≤ P0 < P1 < … < Pk < N.

A subsequence slice (P0, P1, …, Pk) of array A is called arithmetic if the sequence A[P0], A[P1], …, A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequences slices in the array A.


Input Format:

The first and the only argument of input contains an integer array, A of size N.

Output Format:

Return an integer representing the number of arithmetic subsequences in A.

Constraints:

1 <= N <= 1000
-1e5 <= A[i] <= 1e5

Examples:

Input 1:
    A = [2, 4, 6, 8, 10]

Output 1:
    7

Explanation 1:
    All arithmetic subsequence slices are:
        [2,4,6]
        [4,6,8]
        [6,8,10]
        [2,4,6,8]
        [4,6,8,10]
        [2,4,6,8,10]
        [2,6,10]
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Arithmetic Subsequences on Interview Code Editor
Hints
  • Hints are not available for this problem

Discussion


Loading...
Click here to start solving coding interview questions