1 package day20170206; 2 //LeetCode:441. Arranging Coins 3 /* 4  You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins. 5 Given n, find the total number of full staircase rows that can be formed. 6  7 n is a non-negative integer and fits within the range of a 32-bit signed integer. 8  9 Example 1:10 11 n = 512 13 The coins can form the following rows:14 ¤15 ¤ ¤16 ¤ ¤17 18 Because the 3rd row is incomplete, we return 2.19 Example 2:20 21 n = 822 23 The coins can form the following rows:24 ¤25 ¤ ¤26 ¤ ¤ ¤27 ¤ ¤28 29 Because the 4th row is incomplete, we return 3.30 Subscribe to see which companies asked this question.31  */32 public class arrangeCoins441 {33     public static int arrangeCoins(int n) {34         int i=1;35         for(;n>=i;i++){36             n=n-i;37         }38         return i-1;39     }40     //study (k+1)k<=2n--> 4k^2+4k+1<=8n+1--> (2k+1)^2<=8n+141     public static int arrangeCoins2(int n){42         return (int)((Math.sqrt(8.0*n+1)-1)/2);43     }44     //study left right   mid*mid是一个很大的数，0.5要放在前面  left=0和left=1无差45     public static int arrangeCoins3(int n){46         int left=1,right=n;47         int mid=0;48         while(left<=right){49             mid=(left+right)/2;50             if(0.5*mid*(mid+1)>n)51                 right=mid-1;52             else53                 left=mid+1;54         }55         return left-1;56     }57     public static void main(String[] args) {58         // TODO Auto-generated method stub59 60         System.out.println(arrangeCoins(1));61         System.out.println(arrangeCoins(3));62         System.out.println(arrangeCoins(4));63         System.out.println(arrangeCoins(5));64         System.out.println(arrangeCoins(6));65         System.out.println(arrangeCoins(7));66         System.out.println(arrangeCoins(8));67         System.out.println(arrangeCoins(1804289383));68         69         System.out.println(arrangeCoins2(1));70         System.out.println(arrangeCoins2(3));71         System.out.println(arrangeCoins2(4));72         System.out.println(arrangeCoins2(5));73         System.out.println(arrangeCoins2(6));74         System.out.println(arrangeCoins2(7));75         System.out.println(arrangeCoins2(8));76         System.out.println(arrangeCoins2(1804289383));77         78         System.out.println(arrangeCoins3(1));79         System.out.println(arrangeCoins3(3));80         System.out.println(arrangeCoins3(4));81         System.out.println(arrangeCoins3(5));82         System.out.println(arrangeCoins3(6));83         System.out.println(arrangeCoins3(7));84         System.out.println(arrangeCoins3(8));85 86         System.out.println(arrangeCoins3(1804289383));87     }88 89 }