EasyNo. 2176
Count Equal and Divisible Pairs in an Array — LeetCode 2176 Python Solution
- Topics
- Array
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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
- Input
- nums = [3,1,2,2,2,1,3], k = 2
- Output
- 4
- Explanation
- There are 4 pairs that meet all the requirements:
Python solution
class Solution:
def countPairs(self, nums: List[int], k: int) -> int:
ans = 0
for j, y in enumerate(nums):
for i, x in enumerate(nums[:j]):
ans += int(x == y and i * j % k == 0)
return ansComplexity
- Time
- O(n2)where n is the length of the array nums
- Space · auxiliary
- O(1)
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0057 | Insert Interval | Medium |
| 0228 | Summary Ranges | Easy |
| 0485 | Max Consecutive Ones | Easy |
| 0665 | Non-decreasing Array | Medium |
| 0674 | Longest Continuous Increasing Subsequence | Easy |
| 0699 | Falling Squares | Hard |
Frequently asked questions
- How hard is LeetCode 2176. Count Equal and Divisible Pairs in an Array?
LeetCode 2176. Count Equal and Divisible Pairs in an Array is rated Easy on LeetCode.
- What is the time complexity of LeetCode 2176. Count Equal and Divisible Pairs in an Array?
The Python solution on this page runs in O(n2), where n is the length of the array \textit{nums}.
- What is the space complexity of LeetCode 2176. Count Equal and Divisible Pairs in an Array?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2176. Count Equal and Divisible Pairs in an Array cover?
LeetCode 2176. Count Equal and Divisible Pairs in an Array is tagged Array on LeetCode.