25. Elements Appearing More Than N/K Times

Given an array of size n and a value k, print (in ascending order, space-separated) every distinct value whose count in the array is strictly greater than n/k (real division, not integer division). If no value qualifies, print 'None'.

Input: The first line contains n and k, space-separated. The second line contains n space-separated integers. Output: Print the qualifying values in ascending order, space-separated; print 'None' if no value's count exceeds n/k.

1 <= k <= n <= 10^5

This threshold-based filtering is structurally identical to the classic 'majority element' problem (which is really just the special case k=2) - recognizing that connection extends your understanding to a whole family of frequency-threshold problems.

Given an array and a number k, find every value that appears MORE often than one k-th of the array's total size. Brute force: For every distinct value, scan the whole array counting its occurrences directly - this costs O(n) per distinct value, giving O(n²) in the worst case if there are many distinct values. Optimised: A single pass building a frequency hash map counts every value's occurrences simultaneously in O(n) total, rather than re-scanning the array once per distinct value - then a second quick pass over the (much smaller) map of distinct values checks each against the threshold.

Make a single pass over the array, counting the occurrences of every value in a hash map. Then scan the map's entries, keep every value whose count exceeds n/k, and sort the qualifying values in ascending order before printing (or print 'None' if none qualify). This reduces the counting step to a single linear pass instead of a rescan per element, at the cost of O(n) extra space for the map (proportional to the number of distinct values). Time: O(n log n) Space: O(n)

Use the generalized Boyer-Moore ('Misra-Gries') summary algorithm: maintain at most k-1 candidate counters at a time. For each element, if it already has a counter, increment it; else if fewer than k-1 counters are in use, start a new one for it; otherwise, decrement every existing counter by 1, discarding any that hit zero. Any value occurring more than n/k times is guaranteed to survive as a candidate after this pass. Do a second full pass to verify each surviving candidate's true count. This never needs more than k-1 counters at once, which can be considerably less memory than a hash map over all distinct values when k is small, making it the standard space-optimal approach for this exact problem. Time: O(n * k) Space: O(k)

For each element in the array, scan the entire array again to count how many times that value occurs, then check whether the count exceeds n/k, being careful to avoid re-processing a value already checked. This directly implements the definition but repeats a full O(n) scan for every element, giving quadratic behavior overall in the worst case (many distinct values). Time: O(n^2) Space: O(1)

1. Count how many times every distinct value appears in the array, using a hash map. 2. Compute the exact threshold: the array's length divided by k (using real, non-truncated division). 3. Check every distinct value's count against that threshold - keep only the ones whose count is STRICTLY greater. 4. Print the qualifying values in ascending order, or 'None' if nothing qualifies.

Time: O(n) - one pass to count frequencies, plus a pass over the distinct values (bounded by n) to check the threshold. Space: O(n) in the worst case, for the frequency hash map.

k = 1 (threshold becomes n, which no value's count can strictly exceed, so the answer is always 'None'); k = n (threshold is 1, so any value appearing at least twice qualifies); and n = 10^5 (largest, confirming the hashmap-counting approach is O(n)).

Be precise about using REAL division (not integer/truncated division) for the threshold, exactly as the problem states - using integer division here is a subtle, easy-to-miss correctness bug.