2-liner O(sqrt(N)) 3ms, beat 100% with half reduced loop if area is odd (with explanation)

  • 0

    Key Observation:

    1. The optimal width W is simply the largest divisor of area A upper bounded by sqrt(A).
    2. If area A is odd, both L and W must be odd.
    3. Loop on the smaller range [1, sqrt(A)] for W rather than the larger [sqrt(A), N] for L.

    The "2" above is the trick to cut the loop size in half if A is odd:

    • if A is odd, set initial width as the largest odd number upper bounded by sqrt(A), and increment by -2;
    • if A is even, set initial width as (int)sqrt(A) and increment by -1..
        vector<int> constructRectangle(int A) {
          for (int sq = sqrt(A), W = sq+A%2*(sq%2-1); W >= 1; W-=(A%2+1)) 
            if (A%W == 0) return {A/W, W};

Log in to reply

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