O(1) Java solution


  • 4
    Z
    /*
        use solution from 069 - Sqrt(x), compare res * res == num
        time: O(16) = O(1), space: O(1)
    */
    public boolean solution(int num) {
        int root = 0, bit = 1 << 15;
        while (bit > 0) {
            root |= bit;
            if (root > num / root) {    // if root * root > num
                root ^= bit;    // set the bit back to 0
            }
            bit >>= 1;
        }
        return root * root == num;
    }

  • 1

    This is obviously O(log_2(num)).


  • 0
    Z

    @jedihy Hi I just did a quick look at this solution I posted long time ago. But I still think it should be O(1), because the while loop always loop 16 times, which does not change with value of num. Please correct me if I made any mistake.


  • 2

    The number of iterations depends on the bit length of the number. Theoretically, it's O(logn) not O(1).


  • 1

    @jedihy

    This looks like a O(1) algorithm. An integer's bit length won't be longer than 32.


  • 0
    J

    @zzhai If this is O(1), then any algorithms with limited range input should be O(1), which is not definition of Big-Oh!


  • 0
    J

    @zzhai We should think infinite input!


Log in to reply
 

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