Show problems as
Classic problem #2364MediumArrayHash TableMathCounting

Count Number of Bad Pairs

Real-world version: Out of Step Seat Pairs
Tracked in this browser only
Read Count Number of Bad Pairs on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A single row of a theatre is filled from left to right. Seat i, numbering the seats from 0, is held by a guest whose ticket number is tickets[i].

Take any two seats i and j with i < j. The pair is in step when the number of seats between them matches the rise in ticket number, that is when j - i == tickets[j] - tickets[i]. Every other pair is out of step.

Return how many pairs of seats are out of step. A pair is counted once, not once per order, and a seat is never paired with itself.

Examples

Example 1

Input
tickets = [8, 9, 3]
Output
2

The pair of seats 0 and 1 is in step: the seats are 1 apart and the ticket numbers 8 and 9 are also 1 apart. The pair 0 and 2 is out of step, 2 seats apart against a ticket rise of -5, and so is the pair 1 and 2, 1 seat apart against a rise of -6.

Example 2

Input
tickets = [4, 5, 6, 7, 8]
Output
0

The ticket number climbs by exactly one from each seat to the next, so for every one of the ten pairs the seat gap and the ticket rise are the same number.

Example 3

Input
tickets = [3, 4, 3, 4]
Output
4

Seats 0 and 1 are in step, and so are seats 2 and 3, each pair being 1 seat apart with a ticket rise of 1. The other four pairs, namely 0 with 2, 0 with 3, 1 with 2 and 1 with 3, are all out of step.

Constraints

  • 1 <= tickets.length <= 10^5
  • 1 <= tickets[i] <= 10^9
  • The count can exceed the range of a signed 32-bit integer; it stays below 10^10.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_out_of_step(tickets: list[int]) -> int:
Java
public long countOutOfStep(int[] tickets)

More on the same topics