Given an array arr[] of size N, the task is to find the maximum frequency of any array element by incrementing or decrementing each array element by 1 at most once.
Examples:
Input: arr[] = { 3, 1, 4, 1, 5, 9, 2 }
Output: 4
Explanation:
Decrementing the value of arr[0] by 1 modifies arr[] to { 2, 1, 4, 1, 5, 9, 2 }
Incrementing the value of arr[1] by 1 modifies arr[] to { 2, 2, 4, 1, 5, 9, 2 }
Incrementing the value of arr[3] by 1 modifies arr[] to { 2, 2, 4, 1, 5, 9, 2 }
Therefore, the frequency of an array element(arr[0]) is 4 which is the maximum possible.Input: arr[] = { 0, 1, 2, 3, 4, 5, 6 }
Output: 3
Explanation:
Incrementing the value of arr[0] by 1 modifies arr[] to { 1, 1, 2, 3, 4, 5, 6 }
Decrementing the value of arr[2] by 1 modifies arr[] to { 1, 1, 1, 3, 4, 5, 6 }
Therefore, the frequency of an array element(arr[0]) is 3 which is the maximum possible.
Approach: The problem can be solved using Greedy technique. The idea is to find the largest and the smallest element present in the array and calculate the maximum sum of the frequency of three consecutive numbers by iterating all the numbers over the range of array elements. Finally, print the maximum sum obtained. Follow the steps below to solve the problem:
- Find the largest element of the array say, Max.
- Find the smallest element of the array say, Min.
- Calculate the frequency of all array elements over the range [Min, Max] in the array.
- Iterate over the range [Min, Max] and calculate the maximum sum of the frequency of three consecutive numbers.
- Finally, print the maximum sum obtained.
Below is the implementation of the above approach.
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to maximize the frequency // of an array element by incrementing or // decrementing array elements at most once void max_freq( int arr[], int N) { // Stores the largest array element int Max = *max_element(arr, arr + N); // Stores the smallest array element int Min = *min_element(arr, arr + N); // freq[i]: Stores frequency of // (i + Min) in the array int freq[Max - Min + 1] = { 0 }; // Traverse the array for ( int i = 0; i < N; i++) { // Update frequency // of arr[i] freq[arr[i] - Min]++; } // Stores maximum frequency of an // array element by incrementing // or decrementing array elements int maxSum = 0; // Iterate all the numbers over // the range [Min, Max] for ( int i = 0; i < (Max - Min - 1); i++) { // Stores sum of three // consecutive numbers int val = freq[i] + freq[i + 1] + freq[i + 2]; // Update maxSum maxSum = max(maxSum, val); } // Print maxSum cout << maxSum << "\n" ; } // Driver Code int main() { int arr[] = { 3, 1, 4, 1, 5, 9, 2 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call max_freq(arr, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.Arrays; class GFG{ // Function to maximize the frequency // of an array element by incrementing or // decrementing array elements at most once static void max_freq( int arr[], int N) { Arrays.sort(arr); // Stores the largest array element int Max = arr[N - 1 ]; // Stores the smallest array element int Min = arr[ 0 ]; // freq[i]: Stores frequency of // (i + Min) in the array int freq[] = new int [Max - Min + 1 ]; // Traverse the array for ( int i = 0 ; i < N; i++) { // Update frequency // of arr[i] freq[arr[i] - Min]++; } // Stores maximum frequency of an // array element by incrementing // or decrementing array elements int maxSum = 0 ; // Iterate all the numbers over // the range [Min, Max] for ( int i = 0 ; i < (Max - Min - 1 ); i++) { // Stores sum of three // consecutive numbers int val = freq[i] + freq[i + 1 ] + freq[i + 2 ]; // Update maxSum maxSum = Math.max(maxSum, val); } // Print maxSum System.out.println(maxSum); } // Driver Code public static void main (String[] args) { int arr[] = { 3 , 1 , 4 , 1 , 5 , 9 , 2 }; int N = arr.length; // Function call max_freq(arr, N); } } // This code is contributed by AnkThon |
Python3
# Python3 program to implement # the above approach # Function to maximize the frequency # of an array element by incrementing or # decrementing array elements at most once def max_freq(arr, N): # Stores the largest array element Max = max (arr) # Stores the smallest array element Min = min (arr) # freq[i]: Stores frequency of # (i + Min) in the array freq = [ 0 ] * ( Max - Min + 1 ) # Traverse the array for i in range (N): # Update frequency # of arr[i] freq[arr[i] - Min ] + = 1 # Stores maximum frequency of an # array element by incrementing # or decrementing array elements maxSum = 0 # Iterate all the numbers over # the range [Min, Max] for i in range ( Max - Min - 1 ): # Stores sum of three # consecutive numbers val = freq[i] + freq[i + 1 ] + freq[i + 2 ] # Update maxSum maxSum = max (maxSum, val) # Print maxSum print (maxSum) # Driver Code if __name__ = = "__main__" : arr = [ 3 , 1 , 4 , 1 , 5 , 9 , 2 ] N = len (arr) # Function call max_freq(arr, N) # This code is contributed by AnkThon |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to maximize the frequency // of an array element by incrementing or // decrementing array elements at most once static void max_freq( int [] arr, int N) { Array.Sort(arr); // Stores the largest array element int Max = arr[N - 1]; // Stores the smallest array element int Min = arr[0]; // freq[i]: Stores frequency of // (i + Min) in the array int [] freq = new int [Max - Min + 1]; // Traverse the array for ( int i = 0; i < N; i++) { // Update frequency // of arr[i] freq[arr[i] - Min]++; } // Stores maximum frequency of an // array element by incrementing // or decrementing array elements int maxSum = 0; // Iterate all the numbers over // the range [Min, Max] for ( int i = 0; i < (Max - Min - 1); i++) { // Stores sum of three // consecutive numbers int val = freq[i] + freq[i + 1] + freq[i + 2]; // Update maxSum maxSum = Math.Max(maxSum, val); } // Print maxSum Console.WriteLine(maxSum); } // Driver Code public static void Main() { int [] arr = { 3, 1, 4, 1, 5, 9, 2 }; int N = arr.Length; // Function call max_freq(arr, N); } } // This code is contributed by code_hunt. |
Javascript
<script> // Javascript program for the above approach // Function to maximize the frequency // of an array element by incrementing or // decrementing array elements at most once function max_freq(arr, N) { arr.sort(); // Stores the largest array element let Max = arr[N - 1]; // Stores the smallest array element let Min = arr[0]; // freq[i]: Stores frequency of // (i + Min) in the array let freq = []; for (let i = 0; i < Max - Min + 1 ; i++) { freq[i] = 0; } // Traverse the array for (let i = 0; i < N; i++) { // Update frequency // of arr[i] freq[arr[i] - Min]++; } // Stores maximum frequency of an // array element by incrementing // or decrementing array elements let maxSum = 0; // Iterate all the numbers over // the range [Min, Max] for (let i = 0; i < (Max - Min - 1); i++) { // Stores sum of three // consecutive numbers let val = freq[i] + freq[i + 1] + freq[i + 2]; // Update maxSum maxSum = Math.max(maxSum, val); } // Print maxSum document.write(maxSum); } // Driver Code let arr = [ 3, 1, 4, 1, 5, 9, 2 ]; let N = arr.length; // Function call max_freq(arr, N); </script> |
4
Time Complexity: O(N + |Max – Min|), where Max, Min denotes the largest and the smallest array elements respectively
Auxiliary Space: O(|Max – Min|)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!