Find single element when others repeat k times
Company: Molocoads
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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:
```python
find_single_with_k(nums, k) -> int
```
that returns the unique element.
**Examples**
```text
Example 1:
Input: nums = [1, 1, 1, 2, 2, 2, 4, 5, 5, 5], k = 3
Output: 4
Explanation:
- 1 appears 3 times,
- 2 appears 3 times,
- 5 appears 3 times,
- 4 appears exactly once ⇒ answer = 4.
Example 2:
Input: nums = [1, 1, 1, 1, 2, 2, 2, 2, 4, 5, 5, 5, 5], k = 4
Output: 4
Explanation:
- 1, 2, and 5 each appear 4 times,
- 4 appears exactly once ⇒ answer = 4.
```
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`.
Quick Answer: This question evaluates understanding of array indexing, grouping patterns, and algorithmic complexity in the presence of repeated elements and a single outlier within a sorted sequence.