Timeout error when both solutions are O(n)?


  • 0
    J

    This is the first solution I typed up:

    int result = m;
            for(int i = m+1; i < n; i++) {
                result = result ^ i;
            }
            return result;
    

    I got an exception saying that this took too long. Note that this solution is O(n).

    However, this solution worked:

    while (n > m) {
         n = n & n - 1;
    }
    return m & n;
    

    This solution is also O(n), but it ran without getting a timeout exception.

    Could someone please help me understand why the first one failed and the second one didn't?

    Thanks!


  • 0

    That's because the second solution is O(log n).


  • 0
    J

    That's not too informative @StefanPochmann. Could you explain why the second one is O(log n)?


  • 0

    Well in each loop iteration, it deletes the last 1-bit of n. And there can be at most log(n) 1-bits.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.