Painting Arcs to Nearest Neighbors on a Circle
Updated
Problem statement
A circle has length circumference. A position on the circle is the distance you walk clockwise from a fixed starting mark, so it is a whole number from 0 to circumference - 1. You are given the positions of n different points in the array positions, in any order.
Every point finds its nearest other point, measuring distance along the circle (the shorter way around), and paints the arc between itself and that point. A stretch painted by more than one point counts only once. With two points, each point's nearest point is the other one, and both paint the shorter of the two arcs between them.
Return the total length of the painted part of the circle.
The input is chosen so that every point has exactly one nearest point: with three or more points, no point is equally far from the points on its two sides, and with two points, the two arcs between them have different lengths.
Function
paintedLength(circumference: int, positions: int[]) → longExamples
Example 1
circumference = 20positions = [5,0,9,10,16]return = 9In order around the circle the points are 0, 5, 9, 10, 16, so the gaps between neighbours are 5, 4, 1, 6 and 4 (from 16 back around to 0).
- Point
0sits between gaps4and5and paints the4from16to0. - Point
5paints the gap of4to9. - Points
9and10both paint the gap of1between them. - Point
16paints the gap of4to0, which point0already painted.
The painted gaps are 4 + 4 + 1 = 9. The gaps of 5 and 6 stay unpainted.
Example 2
circumference = 10positions = [7,3]return = 4The two arcs between the points have lengths 4 (from 3 to 7) and 6 (from 7 around to 3). Each point's nearest point is the other one, along the shorter arc, so both paint the arc of length 4.
Example 3
circumference = 12positions = [11,4,6,1]return = 4In order the points are 1, 4, 6, 11, with gaps 3, 2, 5 and 2 (from 11 around to 1, passing 0).
Points 1 and 11 both paint the gap of 2 that passes 0, and points 4 and 6 both paint the gap of 2 between them. The gaps of 3 and 5 are each longer than both gaps next to them, so nobody paints them. The answer is 2 + 2 = 4.
Constraints
3 <= circumference <= 10^92 <= positions.length <= 20000 <= positions[i] < circumference- All values in
positionsare different. - Every point has exactly one nearest point along the circle, as described above.
More Susquehanna International Group (SIG) Phone Screen questions
- Dice Sum That Is a Multiple of mPHONE SCREEN · Seen Nov 2026
- Find Median from Data StreamPHONE SCREEN · Seen Nov 2026
- Filter Movies by Inclusive Year RangePHONE SCREEN · Seen Jul 2026
- Best Single Reroll for Five DicePHONE SCREEN · Seen Feb 2026
- Catching the Bus to the MoviePHONE SCREEN · Seen Jan 2026
- Two Dice Summing to a TargetPHONE SCREEN · Seen Jan 2026
- Median of Uniform Draws in an IntervalPHONE SCREEN · Seen Oct 2025
- One Number Is the Average of the Other TwoPHONE SCREEN · Seen Jun 2025
- Which Coin Pattern Shows Up FirstPHONE SCREEN · Seen May 2025
- Random Points Inside One ArcPHONE SCREEN · Seen Jan 2025
Similar questions at other companies
- Light Source Hits: Sample, Compare, and FitOpenAI · PHONE SCREENOpenAI interview questions
- Three Points in a Semicircle: Monte Carlo EstimateSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Maximum Visible DronesAnduril · PHONE SCREENAnduril interview questions
- Optimal Central WarehouseGoogle · ONSITE INTERVIEWGoogle interview questions
- Locate Vehicles with Square QueriesApplied Intuition · PHONE SCREENApplied Intuition interview questions
- Find All Pythagorean TripletsDell Technologies · PHONE SCREENDell Technologies interview questions
- Sort a Quadratic-Transformed ArrayLinkedIn · PHONE SCREENLinkedIn interview questions
- Text Embedding and Vector SearchNike, Inc. · PHONE SCREEN · ONSITE INTERVIEWNike, Inc. interview questions
- Bootstrap Mean and Confidence IntervalAmazon · PHONE SCREEN
- Piecewise Linear Interpolation and ExtrapolationCitadel · PHONE SCREENCitadel interview questions