src/main/java/com/thealgorithms/searches/HowManyTimesRotated.java - master - NikolayIvkin/TheAlgorithms

src/main/java/com/thealgorithms/searches/HowManyTimesRotated.java

63 строки2 KB

mountdisk

chore: fix some comments (#5333)

16 авг 2024, 20:19

16 авг 2024, 20:197c58b19

package com.thealgorithms.searches;

import java.util.Scanner;

/*
    Problem Statement:
    Given an array, find out how many times it has to been rotated
    from its initial sorted position.
    Input-Output:
    Eg. [11,12,15,18,2,5,6,8]
    It has been rotated: 4 times
    (One rotation means putting the first element to the end)
    Note: The array cannot contain duplicates

    Logic:
    The position of the minimum element will give the number of times the array has been rotated
    from its initial sorted position.
    Eg. For [2,5,6,8,11,12,15,18], 1 rotation gives [5,6,8,11,12,15,18,2], 2 rotations
   [6,8,11,12,15,18,2,5] and so on. Finding the minimum element will take O(N) time but, we can  use
   Binary Search to find the minimum element, we can reduce the complexity to O(log N). If we look
   at the rotated array, to identify the minimum element (say a[i]), we observe that
   a[i-1]>a[i]<a[i+1].

    Some other test cases:
    1. [1,2,3,4] Number of rotations: 0 or 4(Both valid)
    2. [15,17,2,3,5] Number of rotations: 3
 */
final class HowManyTimesRotated {
    private HowManyTimesRotated() {
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        System.out.println("The array has been rotated " + rotated(a) + " times");
        sc.close();
    }

    public static int rotated(int[] a) {
        int low = 0;
        int high = a.length - 1;
        int mid = 0; // low + (high-low)/2 = (low + high)/2

        while (low <= high) {
            mid = low + (high - low) / 2;

            if (a[mid] < a[mid - 1] && a[mid] < a[mid + 1]) {
                break;
            } else if (a[mid] > a[mid - 1] && a[mid] < a[mid + 1]) {
                high = mid + 1;
            } else if (a[mid] > a[mid - 1] && a[mid] > a[mid + 1]) {
                low = mid - 1;
            }
        }

        return mid;
    }
}