Implement K-Means and Detect Divisible Subarrays

Solve both coding tasks.

Part A: Implement K-Means Clustering

Implement K-means clustering for a set of points.

Given:

• points: a list of n points, where each point is a list of d numeric coordinates.
• k: the number of clusters.
• max_iterations: the maximum number of Lloyd iterations to run.
• tolerance: stop early if every centroid moves by at most this Euclidean distance.

Use the first k points as the initial centroids. In each iteration:

1. Assign every point to the nearest centroid using squared Euclidean distance. Break ties by choosing the smallest centroid index.
2. Recompute each centroid as the coordinate-wise mean of the points assigned to it.
3. If a cluster becomes empty, keep its centroid unchanged for that iteration.

Return the final centroid coordinates and the cluster assignment for each input point.

Discuss edge cases such as invalid k, duplicate points, empty clusters, and convergence.

Part B: Detect a Divisible-Sum Subarray

Given an integer array nums and a positive integer k, return true if there exists a contiguous subarray of length at least 2 whose sum is divisible by k. Otherwise return false.

A sum is divisible by k if sum % k == 0.

Example:

• Input: nums = [23, 2, 4, 6, 7], k = 6
• Output: true
• Explanation: The subarray [2, 4] has sum 6, which is divisible by 6.

Constraints:

• 1 <= nums.length <= 100000
• 0 <= nums[i] <= 1000000000
• 1 <= k <= 1000000000

Aim for an O(n) solution.

Part 1: Implement K-Means Clustering

Implement Lloyd's K-means clustering algorithm for a list of points. Use the first k points as the initial centroids. In each iteration, assign every point to the nearest centroid using squared Euclidean distance; if two centroids are tied, choose the smaller centroid index. Then recompute each centroid as the coordinate-wise mean of the points assigned to it. If a cluster becomes empty, keep its centroid unchanged for that iteration. Stop early when every centroid moves by at most tolerance in Euclidean distance, or after max_iterations iterations. After finishing, compute assignments one final time using the final centroids and return them. If max_iterations is 0, return the initial centroids and their assignments.

Constraints

• 1 <= n <= 500
• 1 <= d <= 20
• 1 <= k <= n
• 0 <= max_iterations <= 100
• 0.0 <= tolerance
• All points have the same dimension

Examples

Example 1

Input: ([[0, 0], [0, 2], [10, 10], [10, 12]], 2, 10, 0.0)
Output: ([[0.0, 1.0], [10.0, 11.0]], [0, 0, 1, 1])

Explanation: After a few iterations, the first two points form one cluster and the last two form the other.

Example 2

Input: ([[0], [2], [1]], 2, 10, 0.0)
Output: ([[0.5], [2.0]], [0, 1, 0])

Explanation: Point [1] is initially tied between the two centroids and must choose the smaller index.

Hints

1. Write one helper to assign points to centroids, and another step to average points inside each cluster.
2. When a cluster gets no points, do not move that centroid for that iteration.

Part 2: Detect a Divisible-Sum Subarray

Given an integer array nums and a positive integer k, return True if there exists a contiguous subarray of length at least 2 whose sum is divisible by k. Otherwise return False. Aim for an O(n) solution.

Constraints

• 1 <= len(nums) <= 100000
• 0 <= nums[i] <= 1000000000
• 1 <= k <= 1000000000

Examples

Example 1

Input: ([23, 2, 4, 6, 7], 6)
Output: True

Explanation: The subarray [2, 4] sums to 6, which is divisible by 6.

Example 2

Input: ([23, 2, 6, 4, 7], 13)
Output: False

Explanation: No contiguous subarray of length at least 2 has sum divisible by 13.

Hints

1. If two prefix sums have the same remainder modulo k, the sum between them is divisible by k.
2. Store the earliest index where each remainder appears so you can enforce subarray length at least 2.