Q4. Krishna, a nature lover, loves to explore the winding forest trails in his town. However, he often loses his way and struggles to get back to the starting point. To overcome this problem, Krishna uses an array of positive and negative integers. Whenever he comes across a positive integer k at an index i, he moves forward k steps. Conversely, if he comes across a negative integer (-k), he moves backward k steps.

One day, Krishna found himself lost in the forest and was unable to find his way back to the starting point. He wondered if he could somehow detect a cycle in the array that would help him find his way back. This cycle would start and end at the same index and consist only of either forward or backward movements.

Krishna decided to write a program that could detect such a cycle, taking into account that the array was circular, meaning that the last element's next element was the first element, and the first element's previous element was the last element.

Krishna's program had to determine if there was a cycle in the array that met the following conditions :

• The cycle started and ended at the same index.
• The cycle's length was greater than 1.
• All movements in the cycle followed a single direction, either forward or backward.

If such a cycle existed, Krishna's program had to return 1. Otherwise, it had to return 0.

Question Link - Click Here to Solve This Problem

Intuition Behind the Algorithm

The core idea behind the algorithm is to determine if a cycle exists in a given array that represents a series of steps (forward or backward). The unique aspect is that this array is treated as circular, implying that traversing beyond its boundaries loops back around. The challenge is to identify if there's a continuous loop that starts and ends at the same point without reversing direction, using a fast and efficient method.

#include <iostream>
#include <vector>

using namespace std;

// Helper function to calculate the next index in a circular manner
int next(vector<int> a, int i) {
    return (i + a[i] + a.size()) % a.size();
}

// Function to determine if there is a circular loop in the vector
bool CircularLoop(vector<int> v) {
    int n = v.size(); // Get the size of the vector

    // Iterate through each element in the vector
    for (int i = 0; i < n; i++) {
        int slow = i, fast = i; // Initialize slow and fast pointers

        // Skip the current element if it's 0
        if (v[i] == 0)
            continue;

        // Loop to check for a cycle
        while (v[slow] * v[next(v, slow)] > 0 &&
               v[fast] * v[next(v, fast)] > 0 && 
               v[fast] * v[next(v, next(v, fast))] > 0) {
            slow = next(v, slow); // Move the slow pointer
            fast = next(v, next(v, fast)); // Move the fast pointer twice

            // Check if the slow and fast pointers meet
            if (slow == fast) {
                // Cycle is present, but cycle length should be > 1
                if (slow == next(v, slow))
                    break;
                return true; // Cycle detected
            }
        }

        // Resetting the elements to 0 to avoid revisiting
        slow = i;
        int val = v[slow];
        while (val * v[slow] > 0) {
            int x = slow;
            slow = next(v, slow);
            v[x] = 0;
        }
    }

    return false; // No cycle found
}

int main() {
    int n;
    cin >> n; // Read the number of elements

    vector<int> v;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x; // Read each element into the vector
        v.push_back(x);
    }

    cout << CircularLoop(v) << endl; // Output the result of CircularLoop
    
    return 0;
}

Code Walkthrough

• Function Definition: CircularLoop(vector v) takes an integer vector v representing the steps.

• Initialization: The function starts by determining the size of the vector. It then iterates over each element of the vector using a for-loop.

• Cycle Detection: Two pointers, slow and fast, are used for each position in the array. The slow pointer moves one step at a time, while the fast pointer moves two steps. This is similar to the Floyd’s Cycle detection algorithm used in linked lists.

• Direction Consistency Check: The algorithm ensures that all movements (steps) are in the same direction. This is done by checking the product of consecutive elements; if it’s positive, the direction is consistent.

• Detecting the Loop: If the slow and fast pointers meet (slow == fast), a cycle is detected. However, a cycle's length must be greater than 1, so the algorithm checks if the current position is not the same as the next step.

• Resetting Processed Elements: After exploring each potential cycle starting point, the algorithm resets the elements to zero along the path it just traversed. This avoids rechecking the same path.

• Main Function: It reads the number of elements and the elements themselves, then calls CircularLoop and outputs the result.

Time and Space Complexity Analysis

• Time Complexity: The algorithm has a time complexity of O(n), where n is the number of elements in the array. Each element is visited at most twice - once by the slow pointer and once by the fast pointer.

• Space Complexity: The space complexity is O(1), as no extra space is used apart from the input array and a few variables for iteration and indexing.

Key Points of the Algorithm

• Efficiency: The algorithm efficiently finds cycles without examining every possible starting point in detail.
• Cycle Detection: Uses a two-pointer approach to detect cycles.
• Direction Check: Ensures all steps in a cycle follow the same direction.
• Avoids Redundancy: Resets visited elements to zero to prevent reprocessing.

Conclusion

The presented algorithm is an efficient solution for detecting circular loops in an array with consistent direction. It balances the need for thorough cycle detection with the efficiency of not reprocessing elements.