Count Equal and Divisible Pairs in an Array

Count Equal and Divisible Pairs in an Array - Problem

Array Easy

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) where 0 <= i < j < n, such that:

nums[i] == nums[j] (elements are equal)
(i * j) is divisible by k

A pair (i, j) satisfies the conditions if both the values at indices i and j are the same, and the product of their indices is divisible by k.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,1,2,2,2,1,3], k = 2

› Output: 4

💡 Note: Valid pairs: (2,3), (2,4), (3,4), (0,6). All have equal values and index products divisible by 2.

Example 2 — No Valid Pairs

$ Input: nums = [1,2,3,4], k = 1

› Output: 0

💡 Note: No two elements are equal, so no valid pairs exist regardless of divisibility.

Example 3 — All Same Values

$ Input: nums = [5,5,5,5], k = 3

› Output: 2

💡 Note: Equal value pairs: (0,1), (0,2), (0,3), (1,2), (1,3), (2,3). Only (1,2) with 1*2=2 and (0,3) with 0*3=0 are divisible by 3.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i], k ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array with values and divisor k

Process

Find pairs (i,j) where nums[i]==nums[j] and (i*j)%k==0

Output

Count of valid pairs

Key Takeaway

🎯 Key Insight: Only check pairs with equal values, then verify index product divisibility

Asked in

G Google 12 a Amazon 8

The key insight is that we need both equal values and divisible index products. The brute force approach checks all pairs in O(n²) time. The frequency count approach organizes by grouping indices but maintains O(n²) worst-case complexity. Time: O(n²), Space: O(1) for brute force.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(1)	Check every possible pair (i,j) for both equal values and divisible index product
Frequency Count Optimization	O(n²)	O(n)	Group indices by value, then check divisibility for each group

Brute Force - Check All Pairs — Algorithm Steps

Iterate i from 0 to n-2
For each i, iterate j from i+1 to n-1
Check if nums[i] == nums[j] and (i * j) % k == 0
Count valid pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Pairs

Examine all pairs (i,j) where i < j

Verify Conditions

Check nums[i] == nums[j] and (i*j) % k == 0

Count Valid

Count pairs that satisfy both conditions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] == nums[j] && (i * j) % k == 0) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        nums[numsSize++] = num;
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all pairs - outer loop runs n times, inner loop runs up to n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

567 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler