Find single element when others repeat k times

You are given a sorted array of integers nums in non-decreasing order, and an integer k ≥ 2.

Every value in nums appears exactly k times in a row, except for a single value that appears exactly once. Your task is to find and return that single value.

Assume the length of the array is large, and you should aim for an efficient solution.

We define a function:

that returns the unique element.

Examples

You may assume:

• nums.length >= 1 .
• All integers that are not the unique one appear exactly k times.
• Exactly one integer appears only once.

Follow-up 1:

Is there a relation between the array length n = len(nums) and the repetition count k? Express n in terms of k and the number of repeated groups.

(For the intended setup, the correct relation is of the form:

• n = k * m + 1 for some integer m ≥ 1 .)

Explain why this must be true.

Follow-up 2 (binary search):

The array is sorted and organized as groups of size k (except for the single element). Use this structure to design an O(log n) time algorithm (better than O(n)) to find the single element. Describe how to apply binary search over indices to locate the position of the single element, using the grouping pattern implied by k.