有关阶乘的两个问题

系统管理员 2022-05-28 03:53 197阅读 0赞

![20180329093840232][]

//(方法一、判定5的个数O(Nlog(5)N))给定一个非负整数N,返回N!结果的末尾为0的数量
        public static int getZero(int n)
        {
        	 if(n<0)
        	 {
        	 	return 0;
        	 }
        	  int res=0;
        	  int cur=0;
        	  for(int i=5;i<n+1;i+=5)
        	  {
                     cur=i;
                     while(cur%5==0) //计算有多少个5组成
                     {
                     	res++;
                     	cur/=5;
                     }
        	  }
               return res;
        }

![20180329093949761][]

//(方法二:公式法 O(log(5)N))
        public static int  getZero02(int n)
        {
        	  if(n<0)
        	  {
        	  	 return 0;
        	  }
        	  int res=0;
        	  while(n!=0)
        	  {
        	  	  res+=n/5;
                  n/=5;
        	  }
        	  return res;
        }

二、进阶问题解法

//******************进阶问题***********************
        public static int rigthOne01(int n)
        {
        	 if(n<1)
        	 {
        	 	 return -1;
        	 }
        	 int res=0;
        	 while(n!=0)
        	 {
        	 	 n>>>=1;
        	 	 res+=n;
        	 }
        	 return res;
    
        }
    
        public static int rigthOne02(int n)
        {
        	  if(n<1)
        	  {
        	  	 return -1;
        	  }
        	  int temp=n;
        	  int ones=0;
        	  while(temp!=0)
        	  {
        	  	 ones+=(temp&1)!=0?1:0;
        	  	 temp>>>=1;
        	  }
        	  return n-ones;
    
        }

public static void main(String[]args)
    	{
            //System.out.println("Hello");
            int n=10;
            System.out.println(getZero(n));
            System.out.println(getZero02(n));
             
            ///**********进阶问题********************
            int n2=10;
            System.out.println(rigthOne01(n2));
            System.out.println(rigthOne02(n2));
    	   
    	}

![20180329094251706][]

[20180329093840232]: /images/20220528/2fb55473032b4979bb947d114df7c65c.png
[20180329093949761]: /images/20220528/473130657d9341d1b70264b99db3f340.png
[20180329094251706]: /images/20220528/8f11522c75074621bd4e62ddb7acd5b0.png