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.
Return the value that appears once when every other value appears exactly k times.
Constraints
- Inputs are provided as Python literals compatible with the function signature.
- Return a deterministic value exactly matching the requested output.
Examples
Input: ([2, 2, 3, 2], 3)
Expected Output: 3
Explanation: Single 3.
Input: ([0, 1, 0, 1, 0, 1, 99], 3)
Expected Output: 99
Explanation: Includes zero.
Input: ([-4, -4, -4, -7], 3)
Expected Output: -7
Explanation: Negative value.
Input: ([5], 3)
Expected Output: 5
Explanation: Single element.
Hints
- Start with a direct data structure representation.
- Handle edge cases before the main loop.