Dream Job Accelerator - Day 2 of 3 - Job Interviews (By Vikram Anand)

Index For Interviews Preparation
<<< Previous    Next >>>

...

...

...

...

...

...

...

...

...

Find Pairs - Difference of element and index (Easy Complexity) - Basics of Implementation - HackerEarth

Index of "Algorithms: Design and Analysis"

View Problem on HackerEarth
Download Test Cases

All Tracks>Basic Programming> Implementation> Basics of Implementation>

Problem
Given an array 
 of length 
. Find the number of ordered pairs 
 which satisfy the given condition

 should be divisible by 
Input format

The first line contains an integer 
.
The second line of each test case contains 
 space-separated integers, denoting the elements of array 
.
Output format

Print the number of ordered pairs (i, j) which satisfy the above condition in a new line.

Constraints


Sample Input
3
1 2 3
Sample Output
6
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
For every pair 
 in this array where 
, it satisfy the condition in the problem statement. Hence, the answer is 6.

My Code:

N = int(input())
A = list(map(int, input().split()))

diff_dict = {}

for i in range(len(A)):
    key = A[i] - i
    if key not in diff_dict.keys():
        diff_dict[key] = 0
    diff_dict[key] += 1

ans = 0
for v in diff_dict.values():
    ans += v*(v-1)

print(ans)


Result: All Tests Pass

Solution by ChatGPT

Let’s solve this slowly, intuitively, and in a layman-friendly way, then derive the efficient solution.

---

🔍 Problem in simple words

You are given an array A of length N.

You must count ordered pairs (i, j) such that:

1. i ≠ j

2. (A[i] - A[j]) / (i - j) = 1

3. A[i] - A[j] is divisible by (i - j) (this is already implied by condition 2)

---

🧠 Step 1: Understand the equation

The key condition is:

$$\frac{A[i] - A[j]}{i - j} = 1$$

Multiply both sides by (i - j):

$$A[i] - A[j] = i - j$$

Rearrange:

$$A[i] - i = A[j] - j$$

---

💡 Big Insight (this is the trick)

👉 The condition depends only on the value:

$$A[x] - x$$

So:

• Any two indices i and j form a valid pair iff

• A[i] - i == A[j] - j

• and i ≠ j

---

🧩 Step 2: What does this mean practically?

1. Compute A[i] - i for every index

2. Group indices that have the same value

3. If a group has k elements:

   • Number of ordered pairs (i, j) with i ≠ j is:

     $$k \times (k - 1)$$

Why?

• You can choose any i

• Then choose any j except i

• Order matters → (i, j) and (j, i) are different

---

🧪 Example (from the problem)

Input

ini
A = [1, 2, 3]

Indexing from 1:

yaml
i :  1  2  3
A :  1  2  3
A[i] - i → 0  0  0

All values are equal → group size k = 3

Answer:

3 × (3 - 1) = 6

✔️ Matches sample output.

---

🚀 Efficient Algorithm

Why efficiency matters

• N can be as large as 5 × 10⁵

• Brute force O(N²) is impossible

Efficient idea

• Use a hashmap / dictionary

• Count how many times each value of (A[i] - i) appears

---

✅ Python Solution (Efficient & Clean)

python
def solve():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    from collections import defaultdict
    freq = defaultdict(int)

    # Step 1: compute A[i] - i (1-based indexing)
    for i in range(N):
        key = A[i] - (i + 1)
        freq[key] += 1

    # Step 2: count ordered pairs
    ans = 0
    for k in freq.values():
        ans += k * (k - 1)

    print(ans)

---

⏱ Complexity

• Time: O(N)

• Space: O(N)

• Works easily for large constraints

---

🎓 What this problem teaches (important!)

1. Algebraic transformation can simplify complex conditions

2. Pattern recognition (A[i] - i)

3. Turning a math condition into a grouping problem

4. Difference between ordered vs unordered pairs

5. Using hash maps to beat brute force

---

🧠 One-line intuition

“Count how many pairs of indices share the same value of A[i] - i, then count all ordered pairs within those groups.”

---

If you want, I can also:

• Prove correctness formally

• Show a dry run on another example

• Explain why divisibility condition is redundant

• Convert to C++ / Java

Just tell me 🙂

---

how to understand this: If a group has k elements: Number of ordered pairs (i, j) with i ≠ j is: k×(k−1)

Great question — this is a fundamental counting idea, and once it “clicks”, many problems become much easier.

Let’s explain it slowly, visually, and intuitively.

---

🔹 What does “ordered pair (i, j)” mean?

An ordered pair means:

• (i, j) is different from (j, i)

• Order matters

Example:

scss
(1, 2) ≠ (2, 1)

---

🔹 What does “i ≠ j” mean?

You cannot pair an element with itself.

So:

scss
(1, 1), (2, 2), (3, 3) ❌ NOT allowed

---

🔹 Suppose you have a group of k elements

Example:

ini
Group = {a, b, c}
k = 3

---

🔹 Step-by-step counting

Step 1: Choose i

You can pick any element as i.

Number of choices:

nginx
k

For our example:

ini
i = a OR b OR c → 3 choices

---

Step 2: Choose j

Now pick j, but:

• j ≠ i

So:

• Total elements = k

• One element (the chosen i) is not allowed

Number of choices:

nginx
k - 1

Example:

java
If i = a → j ∈ {b, c}
If i = b → j ∈ {a, c}
If i = c → j ∈ {a, b}

---

🔹 Total number of ordered pairs

Multiply the choices:

rust
k choices for i
×
(k − 1) choices for j
=
k × (k − 1)

---

🔹 Example with k = 3

css
( a , b )
( a , c )
( b , a )
( b , c )
( c , a )
( c , b )

Total = 6

Formula:

3 × (3 − 1) = 6

✔️ Matches exactly

---

🔹 Why NOT divide by 2?

Because:

• (i, j) and (j, i) are counted separately

• This is ordered, not unordered

If order did not matter, then the count would be:

nginx
k × (k − 1) / 2

---

🔹 Quick mental shortcut

• Ordered pairs → k × (k − 1)

• Unordered pairs → k × (k − 1) / 2

---

🔹 Where this shows up often

You’ll see this pattern in:

• Pair counting problems

• Graph edges (directed vs undirected)

• Hash grouping problems

• Competitive programming

• Probability & combinatorics

---

🧠 One-sentence intuition

“Pick the first element freely, then pick a different second element.”

That’s all k × (k − 1) means.

---

If you want, I can:

• Draw a diagram

• Compare ordered vs unordered visually

• Show how this applies to another problem

• Give you a small quiz to test understanding

Just tell me 😊