educative.io

Why does Initialisation of fast and slow pointers matter for correctness?

Courses
,
#1

I wrote a code which had the same logic except for the fact that I initialised both slow and fast pointers to square of n. When running the code, test case 19 is failing. I dry ran and I am getting the correct result. If I initialise slow pointer to n and fast pointer to n square then all test cases are passing. I feel there is a mistake here. Initialisation of pointers shouldn’t matter.

Here is the code that I tried.

public static boolean isHappyNumber(int n) {

    // Replace this placeholder return statement with your code
    if (n==1){
        return true;
    }
    int slow = sumOfSquaresOfDigits(n);
    int fast = sumOfSquaresOfDigits(n);
    while( fast != 1 && slow != fast){
        slow = sumOfSquaresOfDigits(slow);
        fast = sumOfSquaresOfDigits(sumOfSquaresOfDigits(fast));
    }

    return fast==1 ;
}

public static int sumOfSquaresOfDigits(int num){
    int result = 0;
    while(num!=0){
        int lastDigit = num%10;
        num = num/10;
        result += Math.pow(lastDigit, 2);
    }
    return result;
}

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Happy Number

1 Like
#2

Hello @SAILAB_SWARNIM,

The initialization of the fast and slow pointers is critical for the correctness of cycle detection algorithms, such as Floyd’s Tortoise and Hare algorithm, which is used to detect cycles in sequences or linked lists. In your solution code, the initialization is done as such:

int slow = sumOfSquaresOfDigits(n);
int fast = sumOfSquaresOfDigits(n);

Here, both slow and fast start at the same value, the square of the digits of n. In the next iteration, slow will be at the second number in the sequence, and fast will be at the third. This is similar to starting a race where one runner starts at the starting line, and the other starts a few meters ahead. In a cycle detection context, this setup can miss a cycle or incorrectly identify one.

For instance, with the number 19, let’s see what happens:

  1. slow starts at sumOfSquaresOfDigits(19) = 82.
  2. fast starts at the same value, 82.
  3. In the next iteration, slow becomes sumOfSquaresOfDigits(82) = 68.
  4. Meanwhile, fast becomes sumOfSquaresOfDigits(sumOfSquaresOfDigits(82)) = sumOfSquaresOfDigits(68) = 100.

In this specific scenario, slow and fast will never meet and are never evaluated in the while condition while(fast != 1 && slow != fast){ ... }, because they started at the same value and are effectively “out of sync” for this sequence. However, if slow started at n and fast at sumOfSquaresOfDigits(n), they would be in sync for detecting cycles.

int slow = n;
int fast = sumOfSquaresOfDigits(n);

This way, slow starts at the beginning of the sequence, and fast starts one step ahead. This alignment is crucial for correctly detecting cycles in the sequence.

I hope this explanation helps you understand why correct initialization of pointers is necessary to write a solution. Feel free to share more suggestions and feedback. We’d be happy to help. Thanks!

Happy learning!