# Check If Array Pairs Are Divisible by k in Java

The problem of checking if array pairs are divisible by a given integer k is a fundamental challenge in algorithmic problem-solving. It finds applications in mathematics, computer science, and cryptography. Understanding and solving the above problem leads to optimized algorithms for tasks like array manipulation and data processing.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5

Output: true

Explanation: The pairs are (1, 9), (2, 8), (3, 7), (4, 6), and (5, 10).

Example 2:

Input: arr = [1,2,3,4,5,6], k = 10

Output: false

Explanation: We can test all possible pairs to see that there is no way to divide arr into three pairs, each with a sum divisible by ten.

## Using Mathematical Approach

The following mathematical approach computes the sum of all elements in an integer array, checks to see if the sum is divisible by a given integer k without leaving any remainder, and returns a boolean value indicating whether the sum is divisible by k.

Here’s an implementation of checking if an array pair is divisible by k using a mathematical approach :

FileName: ArrayPairDivisible.java

`public class ArrayPairDivisible {   public boolean canArrangeMathematical(int[] arr, int k) {     int sum = 0;     // Calculate the sum of all elements in the array     for (int num : arr) {       sum += num;     }     // Check if the sum is divisible by k     return sum % k == 0;   }   public static void main(String[] args) {     ArrayPairDivisible sol = new ArrayPairDivisible();     int[] arr = {1, 2, 3, 4, 5, 10, 6, 7, 8, 9};     int k = 5;     System.out.println( sol.canArrangeMathematical(arr, k));    }}`

Output:

`true`

Complexity analysis: The time complexity is O(n) due to the iterative process of calculating the sum of elements in the input array. The space complexity is constant O(1) due to the use of a few integer variables. The input array is not considered in the analysis, making the code efficient in terms of time and space usage.

## Using Optimized Approach

The following optimized approach determines whether it is possible to arrange elements of an integer array so that the sum of each pair is divisible by a specified integer k.

Here’s an implementation of checking if an array pair is divisible by k using an optimized approach :

FileName: ArrayPairsDivisible1.java

`public class ArrayPairsDivisible1{   public boolean canArrangeArray(int[] nums, int divisor) {     int[] counts = new int[divisor];     for (int num : nums) {       counts[(num % divisor + divisor) % divisor]++;     }     // Check pairs for each possible modulo result except for 0     for (int i = 1; i < divisor; ++i) {       // For a valid pair, the count of modulo I should be equal to the count of modulo (divisor - i)       if (counts[i] != counts[divisor - i]) {         // If they are not equal, the condition is not met, so return false         return false;       }     }     // Check that count of numbers that are exactly divisible by divisor (modulo result is 0)     // is an even number since they need to be paired among themselves     return counts[0] % 2 == 0;   }   public static void main(String[] args) {     ArrayPairsDivisible1 solution = new ArrayPairsDivisible1();     int[] arr = {1, 2, 3, 4, 5, 10, 6, 7, 8, 9};     int k = 5;     System.out.println( solution.canArrangeArray(arr, k));    }}`

Output:

`true`

Complexity analysis: The overall time complexity is O(n + k) due to the sequential nature of both counting and pair-checking phases. The space complexity is O(1), as there is no extra space that grows with the input size.