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.
1public class Main {
2 public static int findSpecialInteger(int[] arr) {
3 int n = arr.length;
4 int count = 1;
5 for (int i = 1; i < n; i++) {
6 if (arr[i] == arr[i-1]) {
7 count++;
8 if (count > n / 4) return arr[i];
9 } else {
10 count = 1;
11 }
12 }
13 return arr[0];
14 }
15
16 public static void main(String[] args) {
17 int[] arr = {1,2,2,6,6,6,6,7,10};
18 System.out.println(findSpecialInteger(arr));
19 }
20}This Java solution follows the same technique, iterating over the array, counting the number of times the same integer appears consecutively. Once it crosses n/4, it returns the integer.
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.