Same Differences Problem

Same Differences Problem — ExecCode Medium DSA Practice

Solve the Same Differences problem on ExecCode. Free online medium DSA practice in Two Pointers. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You are given an integer array a. Positions are 1-based. Return the number of pairs of positions (i, j) with i < j such that a[j] - a[i] = j - i. The count can be large, so use a 64-bit integer. You are given: a — the array in order Return the number of pairs as a 64-bit integer. a[j] - a[i] = j - i is the same statement as a[i] - i = a[j] - j. Count how many earlier positions share that key.

Examples

Input {'a': [1, 2, 3]}; Output 3. Input {'a': [1, 1, 1, 1]}; Output 0. Input {'a': [3, 1, 2, 4]}; Output 1

Constraints

1 <= a.length <= 100000 1 <= a[i] <= 1000000000 The answer fits in a signed 64-bit integer

Practice Same Differences free on ExecCode. Browse DSA problems, topic map, and placement guides.