Preimage Size of Factorial Zeroes Function

Let f(x) be the number of zeroes at the end of x! . (Recall that x! = 1 * 2 * 3 * ... * x , and by convention, 0! = 1 .)
For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has 2 zeroes at the end. Given K , find how many non-negative integers x have the property that f(x) = K .

Example 1:
Input: K = 0
Output: 5
Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.

Example 2:
Input: K = 5
Output: 0
Explanation: There is no x such that x! ends in K = 5 zeroes.

Note:

K will be an integer in the range [0, 10^9] .

제목 설명: 정수 x에 대한 함수 f(x)를 설정하고 x를 되돌려줍니다!끝 0의 개수, K를 정하고 f(x)=K의 x가 몇 개인지 물어보기
생각:
우선 우리는 x를 구성해야 한다고 생각했다.마지막 0은 인자에 2와 5가 포함되거나 인자의 인자에 2와 5가 포함되어야 하기 때문에 f(x)를 계산하려면 1~x의 인자에 포함된 2와 5의 개수만 계산해야 한다.더욱이 x가 적어도 5를 증가시켜야 인자 5의 개수를 증가시킬 수 있다. x가 주로 2를 증가하면 인자 2의 개수를 증가시킬 수 있기 때문에 임의의 x에 대해 1~x의 인자 5의 개수는 반드시 인자 2의 개수보다 크기 때문에 1~x의 인자 5의 개수는 x이다!끝 0의 개수;다시 생각해 보면 5개의 수가 없으면 반드시 적어도 1대2와 5가 나타나기 때문에 임의의 K에 대해 구하는 해는 0이든 5든 x가 f(x)=K를 만든다면 가능한 x의 개수는 5이다.
그리고 x가 f(x)=K를 만드는지 검증하는 방법을 고려해야 한다. 따라서 우리는 이런 x를 찾아서 f(x)=K를 만드는데 이분법을 사용하는 것을 고려해야 한다. 여기서 리코드의 용례가 비교적 크기 때문에 이분의 상한선을 크게 설정해야 한다.
그리고 우리가 생각해야 할 것은 1~x중인자5의 개수를 어떻게 계산하는가이다. 5개의 수마다 하나의 인자5를 증가시키고 25개의 수마다 하나의 인자5를 추가하며 625개의 수마다 5개를 추가한다. 따라서 1~x중인자5의 개수는 x와 5의 멱을 합쳐서 얻을 수 있다.

class Solution {
    public int preimageSizeFZF(int K) {
        if(min(K))
        	return 5;
        return 0;
    }
    
    public boolean min(int n){
    	long left = 0, right = Integer.MAX_VALUE;
    	right *= 100000;
    	while(left < right){
    		long mid = left + (right - left) / 2;
    		long count = 0;
    		long base = 5;
    		//System.out.println(mid);
    		while(base <= mid){
    			count += mid / base;
    			base *= 5;
    		}
    		if(count == n){
    			//System.out.println(mid + "!!");
    			return true;
    		}
    		if(count < n)
    			left = mid + 1;
    		else
    			right = mid - 1;
    	}
    	//System.out.println(left);
    	return false;
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Preimage Size of Factorial Zeroes Function

좋은 웹페이지 즐겨찾기