Check whether exists index 0 <= k < n - 2 such that elements of array A[] moved clockwise by k indexes make a reverse bitonic array.
My approach to do it in O(n) time complexity:
bool is_antibitonicable(int A[], int n) {
// returns if there is such index k that
// after moving clockwise k elements of array
// A[], that array is reverse bitonic
// - strictly decreasing then strictly
// increasing
if (n < 3)
return false;
// if is_increasing[i] == 1 means this part of A[] is increasing,
// == 0 means that part of A[] is decreasing, == -1 default
int is_increasing[3] = { -1, -1, -1 };
for (int i = 0, j; i < n - 1;) {
if (A[i] < A[i + 1]) { // if A[] is increasing
j = 0;
while (j < 3 && is_increasing[j] != -1)
j++;
if (j == 3)
return false;
is_increasing[j] = 1;
while (i < n - 1 && A[i] < A[i + 1])
i++;
}
else if (A[i] > A[i + 1]) { // check if decreasing
j = 0;
while (j < 3 && is_increasing[j] != -1)
j++;
if (j == 3)
return false;
is_increasing[j] = 0;
while (i < n - 1 && A[i] > A[i + 1])
i++;
}
else // sequence of A[] is neither increasing nor decreasing
return false;
}
// if A[] is only increasing/decreasing
if (is_increasing[1] == is_increasing[2])
return false;
// if A[] is increasing->decreasing->increasing check if increasing
// parts can be merged into one increasing sequence
if (is_increasing[0] == 1 && is_increasing[1] == 0 && is_increasing[2] == 1)
return (A[0] > A[n - 1]);
// decreasing->increasing->decreasing
if (is_increasing[0] == 0 && is_increasing[1] == 1 && is_increasing[2] == 0)
return (A[0] < A[n - 1]);
return true; // increasing -> decreasing or opposite
}
I'd be very glad if someone could look at my solution and comment whether it seems correct or how to do it better, any feedback will be appreciated.