Python – Find All Elements in an Array that Appear More Than n/k Times

This problem involves finding all elements in an array that appear more than n/k times, where n is the total number of elements in the array and k is a given divisor. This is a common problem in data structures and algorithms interviews. In this tutorial, we will explain the problem, provide sample inputs and outputs, discuss the solution steps, and present a Python program to solve it.

Problem Statement

Given an array arr of size n and a positive integer k, find all elements in the array that appear more than n/k times.

Sample Input and Output

Example 1:

</>
Copy
Input: arr = [3, 1, 2, 2, 1, 2, 3, 3], k = 4
Output: [2, 3]

Example 2:

</>
Copy
Input: arr = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: []

Solution Approach

To solve this problem, follow these steps:

  1. Count Frequencies: Use a dictionary to count how many times each element appears in the array.
  2. Determine the Threshold: Calculate the threshold as n/k, where n is the size of the array.
  3. Filter Elements: Iterate through the dictionary and select those elements whose frequency is greater than the threshold.
  4. Return the Result: Output the list of elements that meet the condition.

Python Program

</>
Copy
def find_elements(arr, k):
    """
    Finds all elements in 'arr' that appear more than n/k times,
    where n is the number of elements in arr.
    """
    n = len(arr)
    threshold = n / k  # An element must appear more than this many times
    frequency = {}
    
    # Step 1: Count frequency of each element in the array
    for num in arr:
        frequency[num] = frequency.get(num, 0) + 1
        
    # Step 2: Filter out elements that appear more than n/k times
    result = [num for num, count in frequency.items() if count > threshold]
    return result

# Example 1
arr1 = [3, 1, 2, 2, 1, 2, 3, 3]
k1 = 4
print("Input: arr =", arr1, ", k =", k1)
print("Output:", find_elements(arr1, k1))

# Example 2
arr2 = [1, 2, 3, 4, 5, 6, 7]
k2 = 3
print("\nInput: arr =", arr2, ", k =", k2)
print("Output:", find_elements(arr2, k2))

This program uses a dictionary to count the occurrences of each element and then filters the elements based on whether their frequency exceeds n/k. This approach is efficient with a time complexity of O(n) and is easy to understand for beginners.

Conclusion

In this tutorial, we explored how to find all elements in an array that appear more than n/k times. We discussed the problem statement, provided examples, walked through the solution approach, and implemented a Python program to solve the problem.