Given an array of integers elements, find such t that cyclic t-shift operation turns elements into a sorted array If there is no such t, return -1

Viewed 66

The solution that i've been working on so far:

function solution(elements) {
let numOfShifts;
let shift = shiftedArray(elements);
for(i = 0; i < shift.length; i++){
    
    //Here is where i'm getting stuck... how do i continue through the loop even after the first false is returned 
    //until all arrays are checked for equality?
    if(areEqual(shift[i])){
        numOfShifts = i
    }else return -1;
}
return numOfShifts;
};



function shiftedArray(array){
     let shiftedArrays = [];
  for(let i = array.length -1 ; i >= 1; i--){
      // first element is simply a formula to create chunk 1
        let firstElement = array.length - (i % array.length);
        
        //the result of first element.
        let chunk1 = array.slice(firstElement);
        
        //the remaining numbers
        let chunk2 = array.slice(0, firstElement);
        
        //Copy of both chunks now merged and pushed into shifted arrays
        shiftedArrays.push([...chunk1, ...chunk2]);
     };
     return shiftedArrays;
 }

function areEqual(shift){
    let sortedShift = [...shift].sort((a ,b) => {
        return a - b
    });
    
    
    //takes in a single shift and does a deep check to see if the array is equal to sorted version
    if(sortedShift.length === shift.length){
        return sortedShift.every((element, index) => {
            if(element === shift[index]){
                return true;
            }
            return false;
        })
    }
}

console.log(solution([1,4,2,3]));
console.log(solution([[2, 3, 4, 5, 6, 7, 8, 9, 10, 1]]))

How do I keep the for loop running even after the first false is returned from the areEqual() function?

A side note: I understand that this could probably use some refactoring... like, I was working on this with someone earlier and they mentioned how I can simply shift the array by writing a helper function like shiftArray(arr){return arr.push(arr.pop())} but I don't get how that implementation would work considering that all that's returned is the value that was taken out of the array, not the new shifted array.

1 Answers

You may be doing too much work.

Say you have an array A of n integers, zero indexed.

Parse the array from index 0 to n mod n (so 0 twice). Count the number of pairs where the latter integer is less than the former, and store the first index where this happens.

If the count is 1 and the location is k (so A[k] < A[k-1]), then a cyclic shift of either -k or n-k will convert A to a sorted array. If the count is greater than 1 then there's no solution.

E.g., [4,5,0,1,2,3] -- we see k=2 is the only index which has a value below its predecessor, and a cyclic shift of -2 or 4 forms [0,1,2,3,4,5] which is sorted.

Related