FastPrep
Problem · Sorting

How Many Games Did the First Team Win?

Learn this problem
● MediumAmazon logoAmazonINTERNOA
See Amazon hiring insights

Problem statement

Amazon Games is organizing a tournament of pair games. There are two groups, firstTeam and secondTeam, each containing n players. The skill level of the i-th player in each group is firstTeam[i] and secondTeam[i].

For each pair of indices (i, j) with 0 <= i < j < n, the pair (firstTeam[i], firstTeam[j]) competes against (secondTeam[i], secondTeam[j]). The first team wins that game if firstTeam[i] + firstTeam[j] > secondTeam[i] + secondTeam[j].

Return the number of games won by the first team, modulo 109 + 7.

Function

howManyGamesDidTheyWin(n: int, firstTeam: int[], secondTeam: int[]) → int

Examples

Example 1

n = 3firstTeam = [1, 2, 3]secondTeam = [3, 2, 1]return = 1
Example 1 illustration

The possible index pairs are (0, 1), (0, 2), and (1, 2).

  • (0, 1): 1 + 2 = 3 and 3 + 2 = 5, so the first team loses.
  • (0, 2): 1 + 3 = 4 and 3 + 1 = 4, so the first team does not win.
  • (1, 2): 2 + 3 = 5 and 2 + 1 = 3, so the first team wins.

There is 1 winning game.

Constraints

  • 2 <= n <= 105
  • firstTeam.length == secondTeam.length == n
  • 1 <= firstTeam[i], secondTeam[i] <= 109

More Amazon problems

drafts saved locally
public int howManyGamesDidTheyWin(int n, int[] firstTeam, int[] secondTeam) {
 // write your code here
}
n3
firstTeam[1, 2, 3]
secondTeam[3, 2, 1]
expected1
checking account