Given an integer n (possibly negative), return the floor of its cube root. For negative n, return -floor(cbrt(|n|)). Do not use built-in cbrt functions. Solve in O(log n).
Input: An integer n (-10^9 <= n <= 10^9).
Output: Floor of the cube root of n (negative if n < 0).
Input: 27
Output: 3
Explanation: 3^3=27. cbrt(27)=3.Input: 20
Output: 2
Explanation: 2^3=8<=20<27=3^3. Floor cbrt=2.Input: -8
Output: -2
Explanation: cbrt(-8)=-2 exactly.-10^9 <= n <= 10^9