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.
1using System;
2
3class Program {
4 public static int FindSpecialInteger(int[] arr) {
5 int n = arr.Length;
6 int count = 1;
7 for (int i = 1; i < n; i++) {
8 if (arr[i] == arr[i-1]) {
9 count++;
10 if (count > n / 4) return arr[i];
11 } else {
12 count = 1;
13 }
14 }
15 return arr[0];
16 }
17
18 static void Main() {
19 int[] arr = {1,2,2,6,6,6,6,7,10};
20 Console.WriteLine(FindSpecialInteger(arr));
21 }
22}This C# solution uses a loop-based method to count sequences of repeated elements, returning the first that appears more than n/4 times in the sorted array. It ensures O(n) efficiency through the linear scan.
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.