Timeout error when both solutions are O(n)?

  • 0

    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?


  • 0

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

  • 0

    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.