Given an array arr[ ] with even length N, the task is to find the number of cyclic shifts (rotations) possible for this array, such that the first half of array does not contain the maximum element.
Examples:
Input: N = 6, arr[ ] = { 3, 3, 5, 3, 3, 3 }
Output: 3
Explanation: The maximum element here is 5 at index 2. This 5 can be shifted to second half of the array using any of the below three valid right shifts:
- shift by 1: (3, 3, 3, 5, 3, 3)
- shift by 2: (3, 3, 3, 3, 5, 3)
- shift by 3: (3, 3, 3, 3, 3, 5)
Input: N = 6, arr[ ] = {8, 8, 9, 8, 8, 9}
Output: 0
Explanation: Any rotation in the article wont help in removing the maximum element from 1st half, as there are two occurrences of 9 at index 2 and 5. So any rotation will keep atleast one 9 at index 0, 1 or 2.
Naive Approach: The most basic approach to solve this problem, is based on below idea:
Find all rotations of given array. In the end, just return the count of such rotations which do not have the maximum element in first half.
Time Complexity: O(N3) where N^2 is for rotations and N is for finding maximum in each rotation.
Auxiliary Space: O(1)
Efficient Approach: The idea to solve the problem is by traversing the array and some basic concepts of maths.
The idea is to find distance between maximum elements and simply check if the range is greater than half of array size. If yes, rotation is possible, or else rotation is not possible.
For case when rotation is possible, we can find the [range – (n/2)] as the valid number of rotations.
Follow the steps to solve the problem:
- Firstly, find the maximum element
- Then find the maximal ranges between pairs of maximum elements.
- A range with length m adds max(m-frac(N/2)+1, 0) to the 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 find the number of cyclic shiftsint find(int arr[], int N){ int maxele = *max_element(arr, arr + N); int left = -1; int right = -1; // Placing left pointer // On its correct position for (int i = 0; i < N; i++) { if (arr[i] == maxele) { left = i; break; } } // Placing right pointer // On its correct position for (int i = N - 1; i >= 0; i--) { if (arr[i] == maxele) { right = i; break; } } int ans = (N / 2) - (right - left); if (ans <= 0) { return 0; } else { return ans; }}// Driver Codeint main(){ int arr[] = { 3, 3, 5, 3, 3, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << find(arr, N); return 0;} |
Java
// Java program for the above approach.import java.io.*;class GFG { // Function to find the number of cyclic shifts static int find(int arr[], int N) { int maxele = Integer.MIN_VALUE; for(int i = 0; i < N; i++){ maxele = Math.max(arr[i], maxele); } int left = -1; int right = -1; // Placing left pointer // On its correct position for (int i = 0; i < N; i++) { if (arr[i] == maxele) { left = i; break; } } // Placing right pointer // On its correct position for (int i = N - 1; i >= 0; i--) { if (arr[i] == maxele) { right = i; break; } } int ans = (N / 2) - (right - left); if (ans <= 0) { return 0; } else { return ans; } } // Driver Code public static void main (String[] args) { int arr[] = { 3, 3, 5, 3, 3, 3 }; int N = arr.length; // Function call System.out.print(find(arr, N)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach# Function to find the number of cyclic shiftsdef find(arr, N): maxele = max(arr) left = -1 right = -1 # Placing left pointer # On its correct position for i in range(N): if (arr[i] == maxele): left = i break # Placing right pointer # On its correct position for i in range(N - 1, -1, -1): if (arr[i] == maxele): right = i break ans = (N // 2) - (right - left) if (ans <= 0): return 0 else: return ans# Driver Codearr = [3, 3, 5, 3, 3, 3]N = len(arr)# Function callprint(find(arr, N))# This code is contributed by shinjanpatra |
C#
// C# program for the above approach.using System;class GFG { // Function to find the number of cyclic shifts static int find(int[] arr, int N) { int maxele = Int32.MinValue; for (int i = 0; i < N; i++) { maxele = Math.Max(arr[i], maxele); } int left = -1; int right = -1; // Placing left pointer // On its correct position for (int i = 0; i < N; i++) { if (arr[i] == maxele) { left = i; break; } } // Placing right pointer // On its correct position for (int i = N - 1; i >= 0; i--) { if (arr[i] == maxele) { right = i; break; } } int ans = (N / 2) - (right - left); if (ans <= 0) { return 0; } else { return ans; } } // Driver Code public static void Main() { int[] arr = { 3, 3, 5, 3, 3, 3 }; int N = arr.Length; // Function call Console.Write(find(arr, N)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the number of cyclic shifts function find(arr, N) { let maxele = Math.max([...arr]); let left = -1; let right = -1; // Placing left pointer // On its correct position for (let i = 0; i < N; i++) { if (arr[i] == maxele) { left = i; break; } } // Placing right pointer // On its correct position for (let i = N - 1; i >= 0; i--) { if (arr[i] == maxele) { right = i; break; } } let ans = Math.floor(N / 2) - (right - left); if (ans <= 0) { return 0; } else { return ans; } } // Driver Code let arr = [3, 3, 5, 3, 3, 3]; let N = arr.length; // Function call document.write(find(arr, N)); // This code is contributed by Potta Lokesh </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
