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 approachimport sysdef 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 Codea = [ 1, 2, 1, 2 ]# Function callprint(findMaxLen(a))# This code is contributed by Shivam Singh |
C#
// C# program to implement// the above approachusing 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 approachfunction 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> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
