code question 1
← All posts

How to Solve the Amazon Pair Sum Divisible by X Problem (Step-by-Step Guide)

Henry

Problem statement

1. Code Question 1

Amazon is offering a discount on every purchase of a pair of products whose price sum is divisible by x. Given the price of n products in the store, find the number of pairs (i, j) where i < j and price[i] + price[j] is divisible by x.

Example

There are n = 5 products, x = 60 and price = [31, 25, 85, 29, 35].

Five gift boxes with prices 31, 25, 85, 29, 35

The answer is 3 based on the pairs (31, 29), (25, 35), and (85, 35). Each pair sums to a number divisible by x.

Function Description

Complete the function getDiscountPairs in the editor below.

getDiscountPairs has the following parameter(s): int x: sum of pair of integers should be divisible by this number int price[n]: the prices of the products

Returns

int: the number of pairs in the array whose sum is divisible by x

Constraints

  • 1 ≤ x ≤ 2 * 10⁶
  • 1 ≤ n ≤ 10³
  • 1 ≤ price[i] ≤ 10⁶

Understanding the Problem

The first step is making sure you fully understand what's being asked before writing any code. Read the problem carefully and identify the key components: What are the inputs? What are the outputs? What constraints exist?

Next, walk through the given examples manually to simulate the logic. Ask yourself about edge cases like empty inputs, negative numbers, or duplicates. Catching these early shows an interviewer you think rigorously.

Finally, ask clarifying questions. Asking "Can the input be empty?" or "Should I optimize for time or space?" signals maturity and prevents you from solving the wrong problem entirely.

Thought Process

Try to think of similar questions, in this case, what comes into mind is Two Sum. However it is not exactly the same as Two Sum as it requires a product operation.

Now given the examples walk backwards to verify the result. In this case:

(31, 29), (25, 35), and (85, 35)

If you add these up you would get:

(60), (60), (120)

All divisible by x which was 60.

Now think about what would make a pair given just one number. Take 31, in this case you need a number that when added with 31 can be divisible my 60. So 31+29 is divisible by 60.

Extrapolation


Now given the knowledge that 31+29 yields 60, you can then start to think what other numbers can you pair with 31 to yield a pair. And given that they must be multiples of 60, so 60, 120, 180... So valid pairs are 29, 89, 149...

Let's call the first number x and the second number y. The formula for valid pairs is

The valid pair given x is y = n*60-x, or x+y = n*60 where n is any integer from 0 to infinity

Subproblem

Now of course there are infinite combinations because of there are infinite multiples. However you can take a look at a simplified case when every number cannot add up to more than 1 multiple of 60. This now becomes a Two Sum problem with the sum being 60.

This is a modification from the classic Two Sum, so instead of storing the position in the hashmap, we store the number of occurrences.

Connecting the Dots

Now we know the subproblem is easy to solve but given the infinite multiples makes it impossible to make exact comparisons. We need to find a way to simplify or relate the subproblem to the main problem.

Now you can go back to your knowledge toolbox to find a tool that does just that, find if a value is divisible by a number. You will remember that if you take the modulus of the number you get the remainder.

Application

If we take the modulus for all numbers we will get exactly the subproblem. Now we can start coding as we have all the pieces of the puzzle

  1. Use MOD to get the remainder
  2. use the Two Sum to make the pair comparisons

Code

1n = 5
2x = 60
3price = [31, 25, 85, 29, 35]
4
5def getDiscountPairs(x, price):
6    # take the modulus of all the numbers
7    p_mod = [i%x for i in price]
8    # head count of all the pairs
9    count = 0
10    # hashmap of numbers encountered
11    h_map = {}
12
13    for r in p_mod:
14        # find out the complement
15        need = x - r
16        # add to count
17        count += h_map.get(need, 0)
18        h_map[r] = h_map.get(r, 0) + 1
19    return count
20
21print(getDiscountPairs(x, price))

Reference

https://www.interviewdb.io/question/amazon?page=1&name=count-discount-pairs

← Back to all posts