Sponsored
Sponsored
This approach involves scanning the array with a single pass. Given that an element occurring more than 25% will appear as a block, we can count the occurrences of an element until it changes and check the count.
For a given element arr[i], count consecutive occurrences. If it exceeds the threshold (n/4), return that element immediately.
Time Complexity: O(n), as it makes a single pass through the array. Space Complexity: O(1), uses a constant amount of space.
1function findSpecialInteger(arr) {
2 const n = arr.length;
3 let count = 1;
4 for (let i = 1; i < n; i++) {
5 if (arr[i] === arr[i-1]) {
6 count++;
7 if (count > n / 4) return arr[i];
8 } else {
9 count = 1;
10 }
11 }
12 return arr[0];
13}
14
15console.log(findSpecialInteger([1,2,2,6,6,6,6,7,10]));This JavaScript code uses a loop to iterate through the array, counting the occurrences of each integer until it exceeds n/4 times, and returns it.
This approach involves using binary search to take advantage of the sorted nature of the array. By checking elements at regular intervals (n/4), we can identify any elements that repeat in significant blocks more than the threshold.
Instead of scanning the entire array sequentially, we check index positions at specific intervals (n/4, n/2, 3n/4) to find the repeating element.
Time Complexity: O(1) average on small fixed comparisons. Space Complexity: O(1).
This binary search-based approach checks specific, equally distanced indices (n/4 positions) and determines if an element appears more than the 25% threshold by comparing element boundaries within each block.