Loading page…
Practice problem · medium
An ad platform stores every banner creative with its width and height. Partners upload from many design tools, each with its own unit, so a side can be any whole number up to 10^9.
A placement on a page can show any banner of the right shape, scaled up or down. Two banners are interchangeable when one is an exact scaled copy of the other. The platform wants to know how many pairs of banners are interchangeable, to see how much choice each placement really has.
Write count_same_shape_pairs(widths, heights).
i is widths[i] wide and heights[i] tall.i < j have the same shape when widths[i] / heights[i] = widths[j] / heights[j] exactly.int, so use a 64-bit result.Input: widths = [1200, 300, 640, 450, 1600, 600], heights = [900, 250, 480, 300, 1200, 400]
Output: 4Each size is first reduced to its simplest form: divide the width and the height by their greatest common divisor. Equal shapes then give equal keys. The trace counts how many earlier banners have each shape.
| j | Size | Divide by | Shape | Earlier banners with it | Pairs so far |
|---|---|---|---|---|---|
| 0 | 1200 × 900 | 300 | 4 : 3 | 0 | 0 |
| 1 | 300 × 250 | 50 | 6 : 5 | 0 | 0 |
| 2 | 640 × 480 | 160 | 4 : 3 | 1 | 1 |
| 3 | 450 × 300 | 150 | 3 : 2 | 0 | 1 |
| 4 | 1600 × 1200 | 400 | 4 : 3 | 2 | 3 |
| 5 | 600 × 400 | 200 | 3 : 2 | 1 | 4 |
Three banners are 4 : 3, which makes 3 pairs. Two are 3 : 2, which makes 1 more.
Input: widths = [3, 4], heights = [2, 3]
Output: 0A 3 × 2 banner and a 4 × 3 banner look alike, but 3 / 2 = 1.5 and 4 / 3 ≈ 1.33. They are different shapes.
Input: widths = [300, 250, 600], heights = [250, 300, 500]
Output: 1300 × 250 and 600 × 500 are both 6 : 5. The 250 × 300 banner is the same size turned on its side, which is a different shape, 5 : 6.
1 ≤ widths.length = heights.length ≤ 100,000 (banners in the catalogue)1 ≤ widths[i], heights[i] ≤ 10^9 (side lengths in the partner's unit)Testing every pair costs about n × n / 2 checks. At n = 100,000 that is about 5 × 10^9, far over the budget of about 10^8 simple steps a second. One pass with a table of shapes costs about n steps, plus a greatest-common-divisor step for each banner.
Read the values too. The answer can reach about 5 × 10^9, so it needs 64 bits. Sides reach 10^9, so a cross product such as widths[i] × heights[j] reaches 10^18 and also needs 64 bits. Two different shapes can have ratios that differ by only 10^-18, which a floating-point number cannot tell apart.
count_same_shape_pairs · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.