Given an array arr[] consisting of a permutation of first N natural numbers, the task is to find the minimum number of clockwise circular rotations of the array required to maximise the number of elements satisfying the condition arr[i] = i ( 1-based indexing ) where 1 ? i ? N.
Examples:
Input: arr[] = {4, 5, 1, 2, 3}
Output: 3
Explanation: Rotating the array thrice, the array modifies to {1, 2, 3, 4, 5}. All the array elements satisfy the condition arr[i] = i.Input: arr[] = {3, 4, 1, 5, 2}
Output: 2
Explanation: Rotating the array twice, the array modifies to {5, 2, 3, 4, 1}. Three array elements satisfy the condition arr[i] = i, which is the maximum possible for the given array.
Approach: Follow the steps below to solve the problem:
- Initialize two integers maxi and ans, and two arrays new_arr[] and freq[].
- Traverse the array arr[] an for each element, count the number of indices separating it from its correct position, i.e |(arr[i] – i + N) % N|.
- Store the counts for each array element in a new array new_arr[].
- Store the count of frequencies of each element in new_arr[] in the array freq[].
- Print the element ith maximum frequency as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// clockwise array rotations required// to maximize count of array elements// present at indices same as their valuevoid find_min_rot(int arr[], int n){ // Stores count of indices separating // elements from its correct position int new_arr[n + 1]; int maxi = 1, ans = 0; // Stores frequencies of counts of // indices separating int freq[n + 1]; for (int i = 1; i <= n; i++) { freq[i] = 0; } // Count indices separating each // element from its correct position for (int i = 1; i <= n; i++) { new_arr[i] = (arr[i] - i + n) % n; } // Update frequencies of counts obtained for (int i = 1; i <= n; i++) { freq[new_arr[i]]++; } // Find the count with maximum frequency for (int i = 1; i <= n; i++) { if (freq[i] > maxi) { maxi = freq[i]; ans = i; } } // Print the answer cout << ans << endl;}// Driver Codeint main(){ int N = 5; int arr[] = { -1, 3, 4, 1, 5, 2 }; // Find minimum number of // array rotations required find_min_rot(arr, N); return 0;} |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count the number of// clockwise array rotations required// to maximize count of array elements// present at indices same as their valuestatic void find_min_rot(int arr[], int n){ // Stores count of indices separating // elements from its correct position int[] new_arr = new int[n + 1]; int maxi = 1, ans = 0; // Stores frequencies of counts of // indices separating int[] freq = new int[n + 1]; for(int i = 1; i <= n; i++) { freq[i] = 0; } // Count indices separating each // element from its correct position for(int i = 1; i <= n; i++) { new_arr[i] = (arr[i] - i + n) % n; } // Update frequencies of counts obtained for(int i = 1; i <= n; i++) { freq[new_arr[i]]++; } // Find the count with maximum frequency for(int i = 1; i <= n; i++) { if (freq[i] > maxi) { maxi = freq[i]; ans = i; } } // Print the answer System.out.print(ans);} // Driver Codepublic static void main(String[] args){ int N = 5; int[] arr = { -1, 3, 4, 1, 5, 2 }; // Find minimum number of // array rotations required find_min_rot(arr, N);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to count the number of# clockwise array rotations required# to maximize count of array elements# present at indices same as their valuedef find_min_rot(arr, n): # Stores count of indices separating # elements from its correct position new_arr = [0] * (n + 1) maxi = 1 ans = 0 # Stores frequencies of counts of # indices separating freq = [0] * (n + 1) for i in range(1, n + 1): freq[i] = 0 # Count indices separating each # element from its correct position for i in range(1, n + 1): new_arr[i] = (arr[i] - i + n) % n # Update frequencies of counts obtained for i in range(1, n + 1): freq[new_arr[i]] += 1 # Find the count with maximum frequency for i in range(1, n + 1): if (freq[i] > maxi): maxi = freq[i] ans = i # Print the answer print(ans) # Driver Codeif __name__ == '__main__': N = 5 arr = [ -1, 3, 4, 1, 5, 2 ] # Find minimum number of # array rotations required find_min_rot(arr, N) # This code is contributed by jana_sayantan |
C#
// C# program for the above approach using System;class GFG{ // Function to count the number of// clockwise array rotations required// to maximize count of array elements// present at indices same as their valuestatic void find_min_rot(int []arr, int n){ // Stores count of indices separating // elements from its correct position int[] new_arr = new int[n + 1]; int maxi = 1, ans = 0; // Stores frequencies of counts of // indices separating int[] freq = new int[n + 1]; for(int i = 1; i <= n; i++) { freq[i] = 0; } // Count indices separating each // element from its correct position for(int i = 1; i <= n; i++) { new_arr[i] = (arr[i] - i + n) % n; } // Update frequencies of counts obtained for(int i = 1; i <= n; i++) { freq[new_arr[i]]++; } // Find the count with maximum frequency for(int i = 1; i <= n; i++) { if (freq[i] > maxi) { maxi = freq[i]; ans = i; } } // Print the answer Console.Write(ans);} // Driver Codepublic static void Main(String[] args){ int N = 5; int[] arr = { -1, 3, 4, 1, 5, 2 }; // Find minimum number of // array rotations required find_min_rot(arr, N);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the above approach// Function to count the number of// clockwise array rotations required// to maximize count of array elements// present at indices same as their valuefunction find_min_rot(arr, n){ // Stores count of indices separating // elements from its correct position let new_arr = []; let maxi = 1, ans = 0; // Stores frequencies of counts of // indices separating let freq = []; for(let i = 1; i <= n; i++) { freq[i] = 0; } // Count indices separating each // element from its correct position for(let i = 1; i <= n; i++) { new_arr[i] = (arr[i] - i + n) % n; } // Update frequencies of counts obtained for(let i = 1; i <= n; i++) { freq[new_arr[i]]++; } // Find the count with maximum frequency for(let i = 1; i <= n; i++) { if (freq[i] > maxi) { maxi = freq[i]; ans = i; } } // Print the answer document.write(ans);}// Driver code let N = 5; let arr = [ -1, 3, 4, 1, 5, 2 ]; // Find minimum number of // array rotations required find_min_rot(arr, N); // This code is contributed by code_hunt.</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!
