package org.wesome.dsalgo;
public class RotationCount {
public static int rotationCount(int[] arr, int start, int end) {
if (start > end) {
return -1;
}
if (start == end) {
return -1;
}
int mid = (start + end) / 2;
//it's not an end and the mid element is greater than its next.
if (end > mid && arr[mid] > arr[mid + 1])
return (mid + 1);
//it's not start and the previous element is greater than mid.
if (mid > start && arr[mid - 1] > arr[mid])
return mid;
// if the end is greater than mid means it's sorted, rotation is on the left side.
if (arr[end] > arr[mid])
return rotationCount(arr, start, mid - 1);
// else rotation is in right side.
return rotationCount(arr, mid + 1, end);
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import static org.wesome.dsalgo.RotationCount.rotationCount;
public class RotationCountTest {
@Test
void rotationCountTest1() {
int[] arr = new int[]{15, 18, 2, 3, 6, 12};
int rotationCount = rotationCount(arr, 0, arr.length - 1);
Assertions.assertEquals(2, rotationCount);
}
@Test
void rotationCountTest2() {
int[] arr = new int[]{2, 3, 4, 5, 1};
int rotationCount = rotationCount(arr, 0, arr.length - 1);
Assertions.assertEquals(4, rotationCount);
}
@Test
void rotationCountTest3() {
int[] arr = new int[]{1, 2, 3, 4, 5};
int rotationCount = rotationCount(arr, 0, arr.length - 1);
Assertions.assertEquals(-1, rotationCount);
}
}
plugins {
id 'java'
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
repositories {
mavenCentral()
}
dependencies {
testImplementation('org.junit.jupiter:junit-jupiter:5.6.2')
}
test {
useJUnitPlatform()
}