Count Equal and Divisible Pairs in an Array
#1821 Most AskedEasy
Count Equal and Divisible Pairs in an Array #1821 Most Asked
Easy
7 views
Topics:
Arrays
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] and (i * j) is divisible by k.
Example 1:
Input: nums = [3,1,2,2,2,1,3], k = 2 Output: 4 Explanation: There are 4 pairs that meet all the requirements: - nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2. - nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2. - nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2. - nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.
Example 2:
Input: nums = [1,2,3,4], k = 1 Output: 0 Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.
Constraints:
1 <= nums.length <= 1001 <= nums[i], k <= 100
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the possible ranges for the values within the input array and for `k`?
- Can the input array be empty, or can `k` be zero?
- Are there any constraints on the size of the input array `nums`?
- If multiple pairs satisfy the condition, should I return the total count of such pairs?
- Are the elements of the array integers, or could they be floating-point numbers?
Brute Force Solution
Approach
The brute force method for this problem is straightforward. We're going to check every possible pair of numbers in the list to see if they meet our conditions.
Here's how the algorithm would work step-by-step:
- Start by taking the first number in the list and comparing it to every other number in the list.
- For each pair, check if the two numbers are the same.
- If they are the same, also check if the positions of those two numbers, when multiplied, are divisible by a certain number.
- If both conditions are met (the numbers are equal AND their positions multiplied are divisible), then we count that pair.
- After comparing the first number to all other numbers, move to the second number in the list.
- Compare the second number to every number after it in the list (we've already compared it to the numbers before it).
- Repeat the same checks: Are the numbers the same, and is the product of their positions divisible by our special number?
- Continue this process until you've compared every possible pair of numbers in the list.
- Finally, add up the total number of pairs that met both conditions. That's our answer.
Code Implementation
def count_equal_divisible_pairs(numbers, divisor):
count = 0
# Iterate through all possible pairs
for first_index in range(len(numbers)):
for second_index in range(first_index + 1, len(numbers)):
# Check for equality
if numbers[first_index] == numbers[second_index]:
# Calculate product of indices
product_of_indices = first_index * second_index
# Check divisibility. Offset indices for 1-based.
if (product_of_indices + (first_index + 1) * (second_index + 1)) % divisor == 0:
count += 1
return countBig(O) Analysis
Time Complexity
O(n²) – The provided solution iterates through all possible pairs of numbers in the input array nums, which has a size of n. The outer loop implicitly considers each element, and the inner loop compares it with all subsequent elements. This comparison leads to (n-1) + (n-2) + ... + 1 comparisons. The total number of operations is proportional to n*(n-1)/2 which simplifies to n²/2. Therefore, the time complexity is O(n²).
Space Complexity
O(1) – The provided brute force algorithm iterates through the input array using nested loops. It only uses a few integer variables to keep track of the indices and the count of pairs. No additional data structures that scale with the input size N (the number of elements in the array) are used. Therefore, the auxiliary space complexity is constant.
Optimal Solution
Approach
The most efficient way to solve this is by checking each possible pair only once. We can do this by comparing each number in the list to all the numbers that come after it, avoiding redundant checks and making the process faster.
Here's how the algorithm would work step-by-step:
- Take the first number in the list.
- Compare this first number with every other number that comes after it in the list.
- For each pair, check if their positions multiplied together are divisible by a special number.
- Also check to confirm if the numbers are equal.
- If both conditions (divisibility and equality) are met, then count it as a matching pair.
- Move to the next number in the list and repeat the process until all numbers have been checked.
- The final count will represent the total number of pairs that meet the required conditions.
Code Implementation
def count_equal_divisible_pairs(number_list, divisor):
number_of_equal_divisible_pairs = 0
for first_index in range(len(number_list)):
# Iterate through the list to select the first number.
for second_index in range(first_index + 1, len(number_list)):
# Iterate through the rest of the list for the second number.
if number_list[first_index] == number_list[second_index]:
# Check if the numbers at the two indices are equal
if (first_index * second_index) % divisor == 0:
number_of_equal_divisible_pairs += 1
return number_of_equal_divisible_pairsBig(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through each element of the array of size n. For each element, it compares it with all subsequent elements in the array to check for equality and divisibility. In the worst case, for the first element, it will compare with n-1 elements, for the second element, it will compare with n-2 elements, and so on. Therefore, the total number of comparisons is approximately proportional to n * (n-1) / 2, which simplifies to O(n²).
Space Complexity
O(1) – The algorithm iterates through pairs of numbers using nested loops, but it doesn't create any auxiliary data structures like arrays, hash maps, or linked lists. The only extra space used is for storing a few integer variables like loop counters and the count of matching pairs. Therefore, the space used is constant and does not depend on the input size N, the number of elements in the list.
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty input array | The function should return 0 immediately as there are no pairs. |
| Input array with only one element | The function should return 0 since a pair requires at least two elements. |
| Input array with two identical elements and k divides the product of their indices | The function should return 1 as the pair (0,1) is valid if k divides their product. |
| Large array size exceeding memory limits. | Ensure the chosen algorithm has optimal space complexity and avoid storing large intermediate data structures. |
| Large integer values causing potential overflow when calculating products. | Use appropriate data types (e.g., long) or modulo operations to prevent integer overflow. |
| k is zero | Handle this by throwing an exception or returning 0 as division by zero is undefined. |
| k is a large prime number | Ensure that the algorithm does not perform unnecessary calculations that are computationally expensive if 'k' is a large prime. |
| Array contains duplicate indices that also result in a valid pair | Each distinct valid pair (i, j) contributes +1 to the total count. |
Null or empty input array
How to Handle:
The function should return 0 immediately as there are no pairs.
Input array with only one element
How to Handle:
The function should return 0 since a pair requires at least two elements.
Input array with two identical elements and k divides the product of their indices
How to Handle:
The function should return 1 as the pair (0,1) is valid if k divides their product.
Large array size exceeding memory limits.
How to Handle:
Ensure the chosen algorithm has optimal space complexity and avoid storing large intermediate data structures.
Large integer values causing potential overflow when calculating products.
How to Handle:
Use appropriate data types (e.g., long) or modulo operations to prevent integer overflow.
k is zero
How to Handle:
Handle this by throwing an exception or returning 0 as division by zero is undefined.
k is a large prime number
How to Handle:
Ensure that the algorithm does not perform unnecessary calculations that are computationally expensive if 'k' is a large prime.
Array contains duplicate indices that also result in a valid pair
How to Handle:
Each distinct valid pair (i, j) contributes +1 to the total count.
0/1916 Google questions completed
0/1916 completed
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
