Problem Description

You are given an integer array that is sorted in non-decreasing order (smallest to largest). In this array, there is exactly one integer that appears more than 25% of the time. Your task is to find and return that integer.

For example, if the array has 8 elements, any number that appears more than 2 times (since 8 × 0.25 = 2) would be the answer. Since the array is sorted, identical numbers will be grouped together consecutively.

The solution leverages the sorted nature of the array. It iterates through each element arr[i] and checks if it equals the element at position i + ⌊n/4⌋ (where n is the array length). If these two elements are the same, it means this number spans at least 25% of the array length, making it the special integer we're looking for.

The key insight is that if a number appears more than 25% of the time in a sorted array, then any occurrence of that number and the element that is ⌊n/4⌋ positions ahead must be the same number. This is because the number's consecutive occurrences must span at least that distance to constitute more than 25% of the array.

Intuition

Since the array is sorted, all occurrences of the same number are grouped together consecutively. If a number appears more than 25% of the time, it means it occupies more than n/4 positions in the array.

Let's think about what this means geometrically. If we have a number that appears more than n/4 times, and we pick any occurrence of this number at position i, then the position i + n/4 must still contain the same number. Why? Because the consecutive block of this number must be longer than n/4 elements.

For example, in an array of length 12, if a number appears more than 3 times (25% of 12), say it appears 4 times consecutively from index 5 to 8: [..., x, x, x, x, ...]. If we're at index 5 (first occurrence) and jump forward by 3 positions (12/4), we land at index 8, which is still the same number x.

This observation gives us a simple check: for each element at position i, look ahead by ⌊n/4⌋ positions. If we find the same element, we've found our answer. We don't need to count occurrences or use extra space - just a simple comparison exploiting the sorted property and the "more than 25%" constraint.

The beauty of this approach is that we're guaranteed to find the special number because it must form a consecutive block long enough that this "jump ahead by quarter length" test will succeed for at least one starting position within that block.

Solution Approach

The implementation follows a straightforward traversal approach based on our intuition.

We iterate through the array using enumeration to get both the index i and the element value x at each position. For each element, we perform a simple check:

1. Calculate the jump distance as n >> 2, which is equivalent to ⌊n/4⌋ (using bit shift for efficiency)
2. Check if the current element x equals the element at position i + (n >> 2)
3. If they match, we immediately return x as our answer

The algorithm works as follows:

• Start from index 0 and move forward
• At each position i, look ahead by exactly ⌊n/4⌋ positions
• Compare the current element with the element at the look-ahead position
• The first match we find is guaranteed to be the special integer

The bit shift operation n >> 2 is used instead of n // 4 for calculating the quarter length - both give the same result but bit shifting is slightly more efficient.

Since we're only doing a single pass through the array with constant-time lookups, the time complexity is O(n) where n is the length of the array. The space complexity is O(1) as we only use a few variables regardless of input size.

The elegance of this solution lies in its simplicity - no counting, no extra data structures, just a clever use of the problem's constraints (sorted array and >25% occurrence) to find the answer with minimal operations.

Example Walkthrough

Let's walk through a concrete example to see how this solution works.

Consider the array: [1, 2, 2, 6, 6, 6, 6, 7, 10]

• Array length n = 9
• Jump distance = ⌊9/4⌋ = 2
• For a number to appear more than 25% of the time, it needs to appear more than 9 × 0.25 = 2.25 times, so at least 3 times

Now let's trace through the algorithm:

Step 1: i = 0, element = 1

• Look ahead by 2 positions: arr[0 + 2] = arr[2] = 2
• Compare: 1 ≠ 2, not a match, continue

Step 2: i = 1, element = 2

• Look ahead by 2 positions: arr[1 + 2] = arr[3] = 6
• Compare: 2 ≠ 6, not a match, continue

Step 3: i = 2, element = 2

• Look ahead by 2 positions: arr[2 + 2] = arr[4] = 6
• Compare: 2 ≠ 6, not a match, continue

Step 4: i = 3, element = 6

• Look ahead by 2 positions: arr[3 + 2] = arr[5] = 6
• Compare: 6 = 6, match found!
• Return 6

The algorithm correctly identifies 6 as the special integer. Indeed, 6 appears 4 times in the array, which is more than 25% (4/9 ≈ 44%).

Why this works: The number 6 forms a consecutive block from indices 3 to 6. When we start at any position within the first part of this block (indices 3, 4, or 5) and jump ahead by 2 positions, we land within the same block, guaranteeing we'll find a match. Since 6 appears more than n/4 times consecutively, at least one starting position will have its corresponding look-ahead position also containing 6.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. The algorithm iterates through the array once in the worst case. Although the loop may terminate early when a match is found, in the worst-case scenario (when the special integer appears at the end of the array), we need to check up to n - n/4 = 3n/4 elements, which is still O(n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the loop variables i and x, regardless of the input size. No additional data structures are created that scale with the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in the Boundary Check

The Pitfall: A common mistake is forgetting to check if i + quarter_length is within array bounds before accessing arr[i + quarter_length]. Without this check, the code will throw an IndexError when i gets close to the end of the array.

Incorrect Code:

for i, current_element in enumerate(arr):
    # Missing boundary check - will cause IndexError!
    if current_element == arr[i + quarter_length]:
        return current_element

The Solution: Always include the boundary check i + quarter_length < n before accessing the array:

for i, current_element in enumerate(arr):
    if i + quarter_length < n and current_element == arr[i + quarter_length]:
        return current_element

2. Using Incorrect Quarter Calculation for Small Arrays

The Pitfall: For very small arrays (n < 4), using integer division n // 4 gives 0, which means we'd be comparing each element with itself. This could lead to returning the wrong answer in edge cases.

Example Problem:

arr = [1, 2, 2]  # n = 3, quarter_length = 3 // 4 = 0
# Element 2 appears 66% of the time (more than 25%)
# But checking arr[0] == arr[0] would incorrectly return 1

The Solution: The original algorithm actually handles this correctly because:

• For small arrays where an element appears >25%, it will still span the required distance
• Alternative approach: Handle small arrays as a special case:

n = len(arr)
if n == 1:
    return arr[0]
quarter_length = n // 4

3. Misunderstanding the Algorithm's Logic

The Pitfall: Some might think they need to check if an element appears exactly at position i + quarter_length + 1 (adding 1 to ensure "more than" 25%), but this overcomplicates the solution.

Incorrect Thinking:

# Wrong: trying to ensure "more than" 25% by adding 1
if i + quarter_length + 1 < n and current_element == arr[i + quarter_length + 1]:
    return current_element

The Solution: The original approach is correct. If an element appears more than 25% of the time in a sorted array, checking at position i + n//4 is sufficient because:

• The element must span at least this distance to constitute >25%
• The consecutive occurrences guarantee the match will be found

4. Forgetting the Array is Sorted

The Pitfall: Attempting to use complex counting mechanisms or hash maps when the sorted property already provides all needed information.

Overcomplicated Approach:

# Unnecessary complexity - using a counter
from collections import Counter
counter = Counter(arr)
for num, count in counter.items():
    if count > len(arr) // 4:
        return num

The Solution: Leverage the sorted property with the simple look-ahead approach as shown in the original solution. This achieves O(n) time with O(1) space instead of O(n) space for counting.