Funcia
Lv.1countinghashmath

Pairs with Sum Divisible by K

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given non-negative integers nums and a positive k, count pairs i < j with nums[i] + nums[j] divisible by k.

Examples

numskresult
[2, 4, 1, 5, 3]34
[6, 6, 6]43
[1, 2]50

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(nums: int[], k: int) → long

Constraints

  • 1≤1 \le nums.length ≤200,000\le 200{,}000, 0≤0 \le nums[i] ≤109\le 10^9, 1≤1 \le k ≤109\le 10^9
  • The answer can exceed 32 bits.

Expected complexity

Time
O(N)
Space
O(N)

Examples

numskExpected
[2,4,1,5,3]34
[6,6,6]43
[1,2]50

Hint

Hint

Only remainders matter: a value with remainder r pairs with remainder (k - r) % k. Sweep once with a hash map of remainder counts (k is too large for an array). Checking all pairs is O(N2)O(N^2).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251172 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness408verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.