Rotate and delete

Given an array arr integers. Assume sz to be the initial size of the array. Do the following operations exactly sz/2 times. In every kth (1<= k <= sz/2) operation:

• Right-rotate the array clockwise by 1.
• Delete the (n– k + 1)th element from begin.

Now, Return the first element of the array.
Note: Here n keeps on decreasing with every operation.

Examples:

Input: arr = [1, 2, 3, 4, 5, 6]
Output: 3
Explanation: Rotate the array clockwise i.e. after rotation the array arr = [6, 1, 2, 3, 4, 5] and delete the last element that is 5 that will be arr = [6, 1, 2, 3, 4]. Again rotate the array for the second time and deletes the second last element that is 2 that will be A = [4, 6, 1, 3], doing similar operation when we perform 4th operation, 4th last element does not exist. Then we deletes 1st element ie 1 that will be arr = [3, 6]. So, continuing this procedure the last element in arr is 2. So, the output will be 3.

Input: arr = [1, 2, 3, 4]
Output: 2
Explanation: Rotate the vector clockwise i.e. after rotation the vector arr = [4, 1, 2, 3] and delete the last element that is 3 that will be arr = [4, 1, 2]. After doing all the operations, the output will be 2.

Expected Time Complexity: O(n²)
Expected Auxiliary Space: O(1)

Constraints:
1 <= arr.size() <= 10³
1 <= arr[i] <= 10⁶

Approach 01:

class Solution {
public:
    int rotateDelete(std::vector<int>& numbers) {
        int size = numbers.size();
        int halfSize = size / 2;

        bool skipFlag = false;
        int count = 1;

        for (int i = size - 1; i >= 0; i--) {
            if (count == halfSize)
                return numbers[i];
            
            count++;
            if (skipFlag) {
                skipFlag = false;
                continue;
            } else {
                i--;
                skipFlag = true;
            }
        }
        
        return 0; // Default return if no match found
    }
};

class Solution:
    def rotateDelete(self, numbers):
        size = len(numbers)
        halfSize = size // 2

        skipFlag = False
        count = 1

        i = size - 1
        while i >= 0:
            if count == halfSize:
                return numbers[i]
            
            count += 1
            if skipFlag:
                skipFlag = False
            else:
                i -= 1
                skipFlag = True
            i -= 1

        return 0  # Default return if no match found

Time Complexity

• Iterating through the numbers:

  The algorithm uses a single loop to iterate backward through the numbers vector. In the worst case, it will iterate over all elements of the vector once, which takes \(O(n)\), where \(n\) is the size of the numbers vector.

• Skipping elements:

  In each iteration, the algorithm skips every other element based on the skipFlag, but this does not change the overall time complexity because the loop still iterates through the vector in a linear fashion.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the numbers vector.

Space Complexity

• Auxiliary Space:

  The algorithm uses a few integer variables (size, halfSize, count, and skipFlag), all of which require constant space, \(O(1)\). No additional data structures are used.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the algorithm does not use any extra space proportional to the input size.