Java O(1) using newton's method


  • 0
    C

    The idea is use the newton's method on the function f(res)=(1+res)res/2-n
    note
    int t=(res/2
    res-n)/res;
    It is the approximate value but not affect the result.

    public class Solution {
        public int arrangeCoins(int n) {
            int res=n>65535?65535:n;
            while (true){
                if(res%2==0&&res/2*(1+res)<=n)break;
                else if(res%2==1&&(1+res)/2*res<=n)break;
                int t=(res/2*res-n)/res;
                t=t>1?t:1;
                res=res-t;
            }
            return res;
            
        }
    }
    

Log in to reply
 

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