Number Pairs Whose Sum is Multiple of a Number X

$\mathtt{DOWNLOAD\ SOLUTION}$

Task Description

Kelly gives Ashley N chocolates each having a price pi, (where pi is the price of ith chocolate), and an integer X. She asks her to group the N chocolates in to pairs such that sum of prices of chocolates in each pair is a multiple of X.

Output yes if its possible to group the chocolates in to pairs and No if its not possible.

Solution 1: Considering all possible $nC2$ pairs

The first solution is to try to form pairs and satisfies our constraint. If at any point, if the constraint is not satisfied, we will need to Backtrack and try out different pairs.

For the size of array $n$, there are total of $nC2 \approx n^2$ possible combinations. So the complexity will be ${\cal O}(n^2)$.

Solution 2: Optimization of Solution 1

Consider four numbers $a,\ b,\ c,\ d$
Let,

            a + c is a multiple of X
       and, b + d is a multiple of X
    

So the numbers can be paired as $[a,\ c]$ and $[b,\ d]$

Now,what will happen if $a + b$ is also a multiple of X?

  a + c = CONST1 * X
  b + d = CONST2 * X
  a + b = CONST3 * X

  a + b + c + d = (CONST1 + CONST2) * X
  CONST3 * X + (c + d) = (CONST1 + CONST2) * X
  c + d = (CONST1 + CONST2 - CONST3) * X

This proves that (c + d) is also a multiple of X.

So in general, if

• $a$ and $d$ pairs up,
• $a$ pairs up with a set of numbers $S1$ and
• $d$ pairs up with a set of numbers $S2$

Then, $a$ and $d$ can pair up with any number in the sets $S1$ and $S2$.

With this conclusion, we can optimise our Solution 1 by eliminating the Backtrack. We can keep on pairing up numbers. If all numbers have pairs, we can return True. If any number does not have a pair, we can return False.

Time Complexity

Even after the optimization, at worst case, for each element we need to go through all elements. $\therefore$ Total Time complexity is ${\cal O}(n^2)$. The space complexity is ${\cal O}(n)$ for the array paired.

Solution 3: Linear Time Solution

The problem can be solved in linear time by traversing the array only once.

Principle

If sum of two numbers a and b is multiple of a number X,

Then,

      (a % X) + (b % X) = X     if a % x > 0
                        = 0     if a % X == 0
    

So, in order for all numbers to pair up,

      number of elements in the array with modulo X value C  
          == number of elements in the array with module X value X - C
    

Following are the linear time solutions.

Solution Using Array

Solution Using Hash Map

Time Complexity

In this solution, we traverse through the input array only once. Important thing to note here is, the size of the array count is the value of input integer X. So if there is no constraint over the value of X, then the solution could be Pseudo-Polynomial. Otherwise , the overall time complexity is ${\cal O}(n)$. The Space complexity is ${\cal O}(X)$.

---

---

---