Array Pair Sum Divisibility

mediumSave

ArrayCountingHash Table

Given an array of integers and a number k, determine if there exists a pair of distinct elements in the array whose sum is divisible by k. The function should return true if such a pair exists and false otherwise.

Example 1

Input

Output

true

Explanation. Here, 4 + 5 = 9 is divisible by 3. Hence, the output is true.

Example 2

Input

Output

false

Explanation. There are no two numbers in this array whose sum is divisible by 10.

Example 3

Input

Output

true

Explanation. The pair (22, -8) sums to 14, which is divisible by 4. Therefore, the output is true.

Example 4

Input

[
  [
    1
  ],
  5
]

Output

false

Explanation. There is only one element in the array, hence no pair exists.

Example 5

Input

Output

true

Explanation. Several pairs such as (25, 35), (35, -5), and others sum to multiples of 10. Thus, the output is true.

Follow-up: How would you optimize your solution if the array is very large or if it is known that all elements are non-negative?

Constraints:

- The array may contain both positive and negative integers.\n- The value of `k` will be a positive integer.\n- The array will contain at least one element.

Views: 3