Given an array arr[], consisting of N positive integers in the range [1, N], the task is to find the largest minimum distance between any consecutive repetition of an element from any permutation of the given array.
Examples:
Input: arr[] = {1, 2, 1, 3}
Output: 3
Explanation: The maximum possible distance between the repetition is 3, from the permutation {1, 2, 3, 1} or {1, 3, 2, 1}.
Input: arr[] = {1, 2, 3, 4}
Output: 0
Approach: Follow the steps below to solve the problem:
- Store the frequency of each array element.
- Find the element which contains the maximum frequency, say maxFreqElement.
- Count the number of occurrences of elements having a maximum frequency, say maxFreqCount.
- Calculate the required distance by the equation (N- maxFreqCount)/( maxFreqElement- 1))
Below is the implementation of the above approach.
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; int findMaxLen(vector< int >& a) { // Size of the array int n = a.size(); // Stores the frequency of // array elements int freq[n + 1]; memset (freq, 0, sizeof freq); for ( int i = 0; i < n; ++i) { freq[a[i]]++; } int maxFreqElement = INT_MIN; int maxFreqCount = 1; for ( int i = 1; i <= n; ++i) { // Find the highest frequency // in the array if (freq[i] > maxFreqElement) { maxFreqElement = freq[i]; maxFreqCount = 1; } // Increase count of max frequent element else if (freq[i] == maxFreqElement) maxFreqCount++; } int ans; // If no repetition is present if (maxFreqElement == 1) ans = 0; else { // Find the maximum distance ans = ((n - maxFreqCount) / (maxFreqElement - 1)); } // Return the max distance return ans; } // Driver Code int main() { vector< int > a = { 1, 2, 1, 2 }; cout << findMaxLen(a) << endl; } |
Java
// Java program to implement // the above approach class GFG{ static int findMaxLen( int a[], int n) { // Stores the frequency of // array elements int freq[] = new int [n + 1 ]; for ( int i = 0 ; i < n; ++i) { freq[a[i]]++; } int maxFreqElement = Integer.MIN_VALUE; int maxFreqCount = 1 ; for ( int i = 1 ; i <= n; ++i) { // Find the highest frequency // in the array if (freq[i] > maxFreqElement) { maxFreqElement = freq[i]; maxFreqCount = 1 ; } // Increase count of max frequent element else if (freq[i] == maxFreqElement) maxFreqCount++; } int ans; // If no repetition is present if (maxFreqElement == 1 ) ans = 0 ; else { // Find the maximum distance ans = ((n - maxFreqCount) / (maxFreqElement - 1 )); } // Return the max distance return ans; } // Driver Code public static void main(String [] args) { int a[] = { 1 , 2 , 1 , 2 }; int n = a.length; System.out.print(findMaxLen(a, n)); } } // This code is contributed by chitranayal |
Python3
# Python3 program to implement # the above approach import sys def findMaxLen(a): # Size of the array n = len (a) # Stores the frequency of # array elements freq = [ 0 ] * (n + 1 ) for i in range (n): freq[a[i]] + = 1 maxFreqElement = - sys.maxsize - 1 maxFreqCount = 1 for i in range ( 1 , n + 1 ): # Find the highest frequency # in the array if (freq[i] > maxFreqElement): maxFreqElement = freq[i] maxFreqCount = 1 # Increase count of max frequent element elif (freq[i] = = maxFreqElement): maxFreqCount + = 1 # If no repetition is present if (maxFreqElement = = 1 ): ans = 0 else : # Find the maximum distance ans = ((n - maxFreqCount) / / (maxFreqElement - 1 )) # Return the max distance return ans # Driver Code a = [ 1 , 2 , 1 , 2 ] # Function call print (findMaxLen(a)) # This code is contributed by Shivam Singh |
C#
// C# program to implement // the above approach using System; class GFG{ static int findMaxLen( int [] a, int n) { // Stores the frequency of // array elements int [] freq = new int [n + 1]; for ( int i = 0; i < n; ++i) { freq[a[i]]++; } int maxFreqElement = int .MinValue; int maxFreqCount = 1; for ( int i = 1; i <= n; ++i) { // Find the highest frequency // in the array if (freq[i] > maxFreqElement) { maxFreqElement = freq[i]; maxFreqCount = 1; } // Increase count of max // frequent element else if (freq[i] == maxFreqElement) maxFreqCount++; } int ans; // If no repetition is present if (maxFreqElement == 1) ans = 0; else { // Find the maximum distance ans = ((n - maxFreqCount) / (maxFreqElement - 1)); } // Return the max distance return ans; } // Driver Code public static void Main(String[] args) { int [] a = {1, 2, 1, 2}; int n = a.Length; Console.Write(findMaxLen(a, n)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript Program to implement // the above approach function findMaxLen(a) { // Size of the array var n = a.length; // Stores the frequency of // array elements var freq = Array(n+1).fill(0); var i; for (i = 0; i < n; ++i) { freq[a[i]]++; } var maxFreqElement = -2147483648; var maxFreqCount = 1; for (i = 1; i <= n; ++i) { // Find the highest frequency // in the array if (freq[i] > maxFreqElement) { maxFreqElement = freq[i]; maxFreqCount = 1; } // Increase count of max frequent element else if (freq[i] == maxFreqElement) maxFreqCount++; } var ans; // If no repetition is present if (maxFreqElement == 1) ans = 0; else { // Find the maximum distance ans = ((n - maxFreqCount) / (maxFreqElement - 1)); } // Return the max distance return ans; } // Driver Code var a = [1, 2, 1, 2]; document.write(findMaxLen(a)); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!