In computer science, one of the intriguing problems is to find a number that occurs an odd number of times in a sorted array. The challenge becomes interesting when aiming to do this in linear time, O(n). This article delves into this problem, presenting how it can be efficiently solved along with examples and associated subtleties of the solution.

Problem Statement

Given a sorted array, the task is to identify the number that appears an odd number of times while ensuring the solution is linear in terms of time complexity. This task becomes easier because the array is sorted, allowing us to take advantage of the inherent properties of ordered data.

Approach and Solution

Key Observation

In a sorted array, identical elements appear in contiguous positions. Our task then simplifies to scanning through the array and counting the occurrences of each element in the group of contiguous identical numbers.

Algorithm

Here is a step-by-step walkthrough of the algorithm used to solve this problem:

1. Initialize a Counter: Start from the first element, use a counter to keep track of the occurrences of each number.
2. Traverse the Array: As you move through the array, compare the current element to the next element:
   • If they are identical, increment the counter.
   • If they differ, check if the counter is odd. If so, report this number as the answer because it occurs an odd number of times.
   • Reset the counter for the new number.
3. Handle the Last Group: After the loop ends, the last group needs to be checked as it might also be the answer.
4. Time Complexity: The provided solution checks each element only once, ensuring a time complexity of O(n).

Technical Example

Consider a sorted array:

$$A = [1, 1, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6]$$

Here is a breakdown of how we would find the number occurring an odd number of times:

• Step 1: Start with the first element (1), count its occurrences — count = 2 since it appears twice. Move to the next number.
• Step 2: 2 appears once (count = 1) — this is odd, so 2 is our candidate.
• Step 3: Continue to 3, which appears three times (count = 3) — another odd, so 3 is our new candidate.
• Step 4: Move to 4, occurs four times (count = 4) — even, ignore it.
• Step 5: 5 occurs three times (count = 3) — odd, making it another potential candidate.
• Step 6: Finally, 6 occurs twice (count = 2) — even, ignore it.

Thus, the numbers 2, 3, and 5 occur an odd number of times.

Implementation Example in Python

Below is a sample Python implementation of the algorithm:

• Time Complexity: The array is traversed once, resulting in an O(n) complexity.
• Space Complexity: Only a few variables for iteration and counting are used, leading to an O(1) space complexity.