💡 Problem Formulation: The challenge is to find the most frequently occurring number in an array without using additional memory, achieving this in linear O(N) time complexity. Given an array such as [3, 2, 3, 2, 3], we seek to return the value 3 as it appears most frequently.
Method 1: Modify and Check
This method involves modifying the original array by using the values as index positions and incrementing the elements at those positions by the array size. On the second pass, the maximum value found will reveal the most frequent number due to the introduced offsets.
Here’s an example:
def find_max_repeating(arr):
n = len(arr)
for i in range(n):
arr[arr[i] % n] += n
max_index = 0
for i in range(1, n):
if arr[i] > arr[max_index]:
max_index = i
return max_index
# Example usage:
arr = [3, 1, 3, 3, 2]
print(find_max_repeating(arr))Output: 3
This snippet modifies the original array by incrementing elements at index arr[i] % n. Then it iterates again to find the greatest value, which indicates the most frequent element. It’s efficient yet it modifies the original data.
Method 2: Range Check
The Range Check method relies on the fact that numbers lie within a specific range (0 to n-1). By traversing the array and incrementing elements at the index of the current value, the most frequent element can be found with another sweep to locate the highest number.
Here’s an example:
def max_repeating(arr):
n = len(arr)
for i in range(n):
arr[arr[i] % n] += n
return max(enumerate(arr), key=lambda x: x[1])[0]
# Example usage:
arr = [2, 3, 2, 3, 5, 3]
print(max_repeating(arr))Output: 3
Although similar to the first method, it optimizes the second pass by using Python’s max function to find the index with the highest number in one sweep. The downside is the same, it alters the original data.
Method 3: Floyd’s Cycle-Finding Algorithm
Floyd’s Cycle-Finding Algorithm, typically used to detect cycles in a sequence, can be repurposed to solve this problem, as the repeating number introduces a cycle in the context of indexing.
Here’s an example:
def find_repeating_number(arr):
slow = arr[0]
fast = arr[0]
# Phase 1 - finding the intersection point
slow = arr[slow]
fast = arr[arr[fast]]
# Phase 2 - finding the repeating number
slow = arr[0]
while slow != fast:
slow = arr[slow]
fast = arr[fast]
return slow
# Example usage:
arr = [4, 2, 2, 4, 2]
print(find_repeating_number(arr))Output: 2
The code snippet first finds the intersection point in the cycle, then resets one pointer and moves both at the same pace to find the entry point of the cycle, which is the repeating number. This does not alter the original array.
Method 4: Bit Manipulation
When the problem domain allows, bit manipulation exploits bitwise operations to solve the problem without extra space and in linear time, given numbers are represented within a fixed number of bits.
Here’s an example:
def max_repeating_bit(arr):
# Assuming 32-bit integer
n = len(arr)
max_bits = 32
result = 0
for bit in range(max_bits):
bit_count = 0
for num in arr:
if num & (1 < n // 2:
result |= (1 << bit)
return result
# Example usage:
arr = [5, 2, 5, 8, 5]
print(max_repeating_bit(arr))Output: 5
The snippet counts the bits set in each position for all numbers in the range and composes the most occuring number from these bits. However, it’s only applicable when the repeating number occurs more than half of the time in the array.
Bonus One-Liner Method 5: Assume Limited Range
A quick and dirty Python one-liner can solve the problem in specific cases where the number range is limited and the array does not mutate during the process.
Here’s an example:
max_repeating = lambda arr: max(set(arr), key=arr.count) # Example usage: arr = [1, 3, 1, 3, 1, 1] print(max_repeating(arr))
Output: 1
This one-liner utilizes Python’s built-in functions to return the maximum repeating element. However, arr.count() is not O(N) per specification; thus, this method is a trick that doesn’t meet the problem constraints but is included for its simplicity in less stringent contexts.
Summary/Discussion
- Method 1: Modify and Check. Efficiently finds the maximum repeating number by reusing the array for storage, but it alters the original contents. Best when array modification is permissible.
- Method 2: Range Check. Similar to Method 1, it uses array elements as storage to avoid extra space. The variation is in the final step, which is more Pythonic. However, it still modifies the original array.
- Method 3: Floyd’s Cycle-Finding Algorithm. It doesn’t alter the input array and is a clever reuse of an algorithm meant for cycle detection. It’s applicable for repeating elements introducing a cycle-like pattern.
- Method 4: Bit Manipulation. This approach works well when a number is guaranteed to repeat more than half the time; otherwise, its utility is limited.
- Method 5: Assume Limited Range. This is not truly O(N) and does use O(n) space in the form of a set, but it’s a handy shortcut for quick, dirty, non-production code or when data and performance constraints are loosened.