# Leetcode – Element Appearing More Than 25% In Sorted Array Solution

The problem titled “Element Appearing More Than 25% In Sorted Array” on Leetcode poses an interesting challenge. It may initially seem simple due to the sorted nature of the array, but the constraints related to time complexity make it a noteworthy problem to explore in detail. In this guide, we will discuss various ways to solve this problem using Python.

1. Problem Description
2. Naive Approach: Brute-force Algorithm
3. Optimized Approach 1: Counting Sequences
4. Testing and Validation
5. Time and Space Complexity Analysis
6. Conclusion

## 1. Problem Description

You’re given a sorted integer array, arr, where the condition is that an integer x will appear more than 25% of the time in the array. Your task is to find and return that integer x.

### Constraints:

• The array is non-empty and has a length in the range [1,10^4].
• The array contains integers in the range [−10^5,10^5].

### Example:

Input: arr = [1, 2, 2, 6, 6, 6, 6, 7, 10]

Output: 6

## 2. Naive Approach: Brute-force Algorithm

### Algorithm:

1. Initialize a counter variable to keep track of occurrences.
2. Iterate through the sorted array and count consecutive similar numbers.
3. If a number occurs more than 25% of the time, return that number.

### Python Code:

def findSpecialInteger(arr):
threshold = len(arr) // 4
count = 1

for i in range(1, len(arr)):
if arr[i] == arr[i - 1]:
count += 1
if count > threshold:
return arr[i]
else:
count = 1

return arr

print(findSpecialInteger([1, 2, 2, 6, 6, 6, 6, 7, 10]))  # Output should be 6

## 3. Optimized Approach 1: Counting Sequences

Since the array is sorted, if a number occurs more than 25% of the time, then one of its instances will definitely appear at an index that is a multiple of the array’s length divided by 4.

### Algorithm:

1. Calculate the threshold index threshold_idx = len(arr) // 4.
2. Check the numbers at indices threshold_idx, 2 * threshold_idx, 3 * threshold_idx and so on.

### Python Code:

def findSpecialInteger(arr):
threshold_idx = len(arr) // 4

for i in range(threshold_idx, len(arr)):
if arr[i] == arr[i - threshold_idx]:
return arr[i]

return -1  # Should never reach this point based on problem constraints

print(findSpecialInteger([1, 2, 2, 6, 6, 6, 6, 7, 10]))  # Output should be 6

## 4. Testing and Validation

While testing, ensure that:

1. The array is sorted.
2. Test with edge cases like minimum and maximum array lengths.
3. Include negative numbers in your test cases.

## 5. Time and Space Complexity Analysis

1. Naive Approach:
• Time Complexity: O(n)
• Space Complexity: O(1)
2. Optimized Approach 1:
• Time Complexity: O(n)
• Space Complexity: O(1)

## 6. Conclusion

In this guide, we have discussed multiple approaches to solve the “Element Appearing More Than 25% In Sorted Array” problem on Leetcode. We started with a naive approach and then discussed an optimized method. It’s always crucial to consider time and space complexities to come up with the most efficient solution.