Maximum Frequency by replacing with elements in a given range
Given a 0-indexed array arr[] of N positive integers and two integers K and X. Find the maximum frequency of any element(not necessary to be present in the array) you can make after performing the below operation at most K times-
- Choose an index i and replace arr[i] with any integer from the range [arr[i] – X , arr[i] + X]
Note: You are allowed to operate on each index at most once.
Examples:
Input: N = 4, K = 2, X = 2, arr[] = {1, 2, 3, 4}
Output: 3
Explanation: After performing the operation on index 1 and 2. Modified array is {1, 1, 1, 4} so the maximum frequency of 1 is 3. It can be proven that we can’t make the frequency of any element greater than 3.Input: N = 5, K = 3, X = 2, arr[] = {1, 3, 8, 12, 18}
Output: 2
Explanation: After performing the operation on index 0. Modified array is {3, 3, 8, 12, 18}, So the maximum frequency that can be made is 2.
Approach: To solve the problem, follow the below idea:
The main idea is to calculate frequency of each element and iterate through each unique element in the array, considering the range of possible values after the operation mentioned i.e. [arr[i] – X , arr[i] + X], and calculating the maximum frequency achievable for each element using lower bound and upper bound. The result is the maximum frequency among all elements.
Step-by-step algorithm:
- Create a frequency map (dit) to store the count of each element in the array.
- Create sets (s and reach) to store unique elements and their corresponding reachable values after the operation.
- Combine the sets to form a set of all potential values (s).
- Create a sorted array (sortedArr) from the original array.
- Iterate through each unique element in the set s.
- Calculate the upper and lower bounds in the sorted array for the range of values after the operation.
- Determine the number of operations that can be performed for the given element (operations).
- Update the maximum frequency achievable for the current element.
- Return the maximum frequency among all elements.
Below is the implementation of the algorithm:
// C++ Implementation
#include <bits/stdc++.h>
using namespace std;
// Function to find index of upper bound element
int upperBound(const vector<int>& arr, int target)
{
return upper_bound(arr.begin(), arr.end(), target)
- arr.begin();
}
// Function to find index of lower bound element
int lowerBound(const vector<int>& arr, int target)
{
return lower_bound(arr.begin(), arr.end(), target)
- arr.begin();
}
// Function to find element with maximum Frequency
int MaxFrequency(int N, vector<int>& arr, int K, int X)
{
// Store the elements frequency in map
unordered_map<int, int> dit;
for (int t : arr) {
dit[t]++;
}
// Store the addition in set
unordered_set<int> s, reach;
for (int e : arr) {
s.insert(e);
reach.insert(e + X);
}
s.insert(reach.begin(), reach.end());
vector<int> sortedArr(arr.begin(), arr.end());
sort(sortedArr.begin(), sortedArr.end());
int ans = 1;
// For each entry in set find the index of
// lower bound and upper bound
for (int e : s) {
int upper = upperBound(sortedArr, e + X);
int lower = lowerBound(sortedArr, e - X);
int operations = min(upper - lower - dit[e], K);
// Update the maximum frequency element
ans = max(ans, operations + dit[e]);
}
// Return maxx
return ans;
}
// Driver code
int main()
{
int n = 4;
int k = 2;
int x = 2;
vector<int> arr = { 1, 2, 3, 4 };
// Function call
cout << MaxFrequency(n, arr, k, x);
return 0;
}
import java.util.*;
public class MaxFrequency {
// Function to find index of upper bound element
static int upperBound(List<Integer> arr, int target) {
return Collections.binarySearch(arr, target, Comparator.naturalOrder());
}
// Function to find index of lower bound element
static int lowerBound(List<Integer> arr, int target) {
return Collections.binarySearch(arr, target, Comparator.naturalOrder());
}
// Function to find element with maximum Frequency
static int maxFrequency(int N, List<Integer> arr, int K, int X) {
// Store the elements frequency in map
Map<Integer, Integer> dit = new HashMap<>();
for (int t : arr) {
dit.put(t, dit.getOrDefault(t, 0) + 1);
}
// Store the addition in set
Set<Integer> s = new HashSet<>();
Set<Integer> reach = new HashSet<>();
for (int e : arr) {
s.add(e);
reach.add(e + X);
}
s.addAll(reach);
List<Integer> sortedArr = new ArrayList<>(arr);
Collections.sort(sortedArr);
int ans = 1;
// For each entry in set find the index of
// lower bound and upper bound
for (int e : s) {
int upper = upperBound(sortedArr, e + X);
int lower = lowerBound(sortedArr, e - X);
int operations = Math.min(upper - lower - dit.getOrDefault(e, 0), K);
// Update the maximum frequency element
ans = Math.max(ans, operations + dit.getOrDefault(e, 0));
}
// Return max
return ans;
}
// Driver code
public static void main(String[] args) {
int n = 4;
int k = 2;
int x = 2;
List<Integer> arr = Arrays.asList(1, 2, 3, 4);
// Function call
System.out.println(maxFrequency(n, arr, k, x));
}
}
// This code is contributed by shivamgupta310570
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
// Function to find index of upper bound element
static int UpperBound(List<int> arr, int target)
{
return arr.BinarySearch(target);
}
// Function to find index of lower bound element
static int LowerBound(List<int> arr, int target)
{
return arr.BinarySearch(target);
}
// Function to find element with maximum Frequency
static int MaxFrequency(int N, List<int> arr, int K, int X)
{
// Store the elements frequency in Dictionary
Dictionary<int, int> dict = new Dictionary<int, int>();
foreach (int t in arr)
{
if (dict.ContainsKey(t))
dict[t]++;
else
dict[t] = 1;
}
// Store the addition in HashSet
HashSet<int> s = new HashSet<int>();
HashSet<int> reach = new HashSet<int>();
foreach (int e in arr)
{
s.Add(e);
reach.Add(e + X);
}
s.UnionWith(reach);
List<int> sortedArr = new List<int>(arr);
sortedArr.Sort();
int ans = 1;
// For each entry in set find the index of
// lower bound and upper bound
foreach (int e in s)
{
int upper = UpperBound(sortedArr, e + X);
int lower = LowerBound(sortedArr, e - X);
int operations = Math.Min(upper - lower - (dict.ContainsKey(e) ? dict[e] : 0), K);
// Update the maximum frequency element
ans = Math.Max(ans, operations + (dict.ContainsKey(e) ? dict[e] : 0));
}
// Return max
return ans;
}
// Driver code
static void Main(string[] args)
{
int n = 4;
int k = 2;
int x = 2;
List<int> arr = new List<int> { 1, 2, 3, 4 };
// Function call
Console.WriteLine(MaxFrequency(n, arr, k, x));
}
}
// JavaScript Implementation
// Function to find index of upper bound element
function upperBound(arr, target) {
let i = 0;
let length = arr.length;
while (i < length) {
let mid = i + Math.floor((length - i) / 2);
if (arr[mid] <= target) {
i = mid + 1;
} else {
length = mid;
}
}
return i;
}
// Function to find index of lower bound element
function lowerBound(arr, target) {
let i = 0;
let length = arr.length;
while (i < length) {
let mid = i + Math.floor((length - i) / 2);
if (arr[mid] < target) {
i = mid + 1;
} else {
length = mid;
}
}
return i;
}
// Function to find element with maximum Frequency
function maxFrequency(N, arr, K, X) {
// Store the elements frequency in map
let dit = new Map();
for (let t of arr) {
dit.set(t, (dit.get(t) || 0) + 1);
}
// Store the addition in set
let s = new Set();
let reach = new Set();
for (let e of arr) {
s.add(e);
reach.add(e + X);
}
s = new Set([...s, ...reach]);
let sortedArr = arr.slice().sort((a, b) => a - b);
let ans = 1;
// For each entry in set find the index of
// lower bound and upper bound
for (let e of s) {
let upper = upperBound(sortedArr, e + X);
let lower = lowerBound(sortedArr, e - X);
let operations = Math.min(upper - lower - (dit.get(e) || 0), K);
// Update the maximum frequency element
ans = Math.max(ans, operations + (dit.get(e) || 0));
}
// Return max
return ans;
}
// Driver code
let n = 4;
let k = 2;
let x = 2;
let arr = [1, 2, 3, 4];
// Function call
console.log(maxFrequency(n, arr, k, x));
# Python Implementation
from typing import List
from collections import defaultdict
# Function to find index of upper bound element
def upper_bound(arr: List[int], target: int) -> int:
i = 0
length = len(arr)
while i < length:
mid = i + (length - i) // 2
if arr[mid] <= target:
i = mid + 1
else:
length = mid
return i
# Function to find index of lower bound element
def lower_bound(arr: List[int], target: int) -> int:
i = 0
length = len(arr)
while i < length:
mid = i + (length - i) // 2
if arr[mid] < target:
i = mid + 1
else:
length = mid
return i
# Function to find element with maximum Frequency
def max_frequency(N: int, arr: List[int], K: int, X: int) -> int:
# Store the elements frequency in map
dit = defaultdict(int)
for t in arr:
dit[t] += 1
# Store the addition in set
s = set()
reach = set()
for e in arr:
s.add(e)
reach.add(e + X)
s = s.union(reach)
sorted_arr = sorted(arr)
ans = 1
# For each entry in set find the index of
# lower bound and upper bound
for e in s:
upper = upper_bound(sorted_arr, e + X)
lower = lower_bound(sorted_arr, e - X)
operations = min(upper - lower - dit[e], K)
# Update the maximum frequency element
ans = max(ans, operations + dit[e])
# Return max
return ans
# Driver code
if __name__ == "__main__":
n = 4
k = 2
x = 2
arr = [1, 2, 3, 4]
# Function call
print(max_frequency(n, arr, k, x))
Output
3
Time Complexity: O(N log N), where N is the size of input array arr[].
Auxiliary Space: O(N)