🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
This blog post addresses the problem of determining the rotation count in a rotated sorted array. When a sorted array is rotated around a pivot, our task is to find out how many times the array has been rotated.
Problem
Given an array of distinct numbers sorted in ascending order, which has been rotated k times around a pivot, find the value of k (the number of rotations).
Example 1:
Input: a = [5, 7, 9, 1, 3] Output: 3 Explanation: The original array must be [1, 3, 5, 7, 9], rotated 3 times.
Example 2:
Input: a = [4, 6, 8, 10, 0, 1, 2] Output: 4 Explanation: The original array would be [0, 1, 2, 4, 6, 8, 10], rotated 4 times.
Example 3:
Input: a = [5, 10, 15, 20] Output: 0 Explanation: The array has not been rotated.
2. Solution Steps
1. Apply binary search to find the rotation point (pivot) where the array has been rotated.
2. The index of the minimum element in the array gives the rotation count.
3. Handle the edge case where the array is not rotated at all.
3. Code Program
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] a1 = {5, 7, 9, 1, 3};
System.out.println("Rotation count: " + findRotationCount(a1));
int[] a2 = {4, 6, 8, 10, 0, 1, 2};
System.out.println("Rotation count: " + findRotationCount(a2));
int[] a3 = {5, 10, 15, 20};
System.out.println("Rotation count: " + findRotationCount(a3));
}
// Method to find the rotation count in the array
public static int findRotationCount(int[] a) {
int start = 0, end = a.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (a[mid] > a[end]) {
start = mid + 1;
} else {
end = mid;
}
}
return start; // The index of the minimum element is the rotation count
}
}
Output:
Rotation count: 3 Rotation count: 4 Rotation count: 0
Explanation:
The findRotationCount method uses a modified binary search to find the index of the smallest element, which is the pivot point of rotation.
In the first example, [5, 7, 9, 1, 3], the smallest element is 1 at index 3, indicating the array was rotated 3 times.
Similarly, for [4, 6, 8, 10, 0, 1, 2], the rotation count is 4. When the array is not rotated like in [5, 10, 15, 20], the rotation count is 0.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment