संख्याओं के पीछे के शून्यों की गणना करने के परिणामस्वरूप फैक्टोरियल

Question

परिणामस्वरूप मैं संख्याओं के पीछे शून्यों को गिनने की कोशिश कर रहा हूं जो तथ्यों से उत्पन्न होते हैं (जिसका अर्थ है कि संख्याएं काफी बड़ी हैं)। निम्नलिखित कोड संख्या लेता है, संख्या के फैक्टोरियल की गणना करता है, और पिछली शून्यों की गणना करता है। हालांकि, जब संख्या 25 जितनी बड़ी है !, numZeros काम नहीं करते हैं।

public static void main(String[] args) { 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    double fact; 
    int answer; 

    try { 
     int number = Integer.parseInt(br.readLine()); 
     fact = factorial(number); 
     answer = numZeros(fact); 
    } 
    catch (NumberFormatException e) { 
     e.printStackTrace(); 
    } catch (IOException e) { 
     e.printStackTrace(); 
    } 
} 

public static double factorial (int num) { 
    double total = 1; 
    for (int i = 1; i <= num; i++) { 
     total *= i; 
    } 
    return total; 
} 

public static int numZeros (double num) { 
    int count = 0; 
    int last = 0; 

    while (last == 0) { 
     last = (int) (num % 10); 
     num = num/10; 
     count++; 
    } 

    return count-1; 
} 

मैं इस कोड की दक्षता के बारे में चिंता नहीं कर रहा हूँ, और मुझे पता है कि इस कोड को बेहतर बनाने की दक्षता के लिए कई तरीके हैं। जो मैं समझने की कोशिश कर रहा हूं वह यह है कि 25 से अधिक संख्याओं की संख्याओं का पिछला भाग क्यों गिन रहा है! काम नहीं कर रहा।

कोई विचार?

Answer 1

आपका काम भाज्य लेकिन शून्यों की संख्या की गणना करने के लिए नहीं है। एक अच्छा समाधान http://en.wikipedia.org/wiki/Trailing_zeros से सूत्र (जो आप को साबित करने की कोशिश कर सकते हैं)

def zeroes(n): 
    i = 1 
    result = 0 
    while n >= i: 
     i *= 5 
     result += n/i # (taking floor, just like Python or Java does) 
    return result 

आशा है कि आप जावा को यह अनुवाद कर सकते हैं का उपयोग करता है। यह बस [एन/5] + [एन/25] + [एन/125] + [एन/625] + ... की गणना करता है और जब विभाजक एन से बड़ा हो जाता है तो बंद हो जाता है।

BigIntegers का उपयोग न करें। यह एक बोझोसॉर्ट है। इस तरह के समाधानों को बड़ी संख्या के लिए सेकंड के समय की आवश्यकता होती है।

Answer 2

आपको केवल यह जानने की ज़रूरत है कि उत्पाद में कितने 2s और 5s हैं। यदि आप पिछली शून्यों की गिनती कर रहे हैं, तो आप वास्तव में गिन रहे हैं "दस इस संख्या को कितनी बार विभाजित करता है?"। यदि आप एन का प्रतिनिधित्व करते हैं! क्यू * (2^ए) * (5^बी) जहां क्यू 2 या 5 से विभाजित नहीं है। फिर दूसरी अभिव्यक्ति में न्यूनतम ए और बी लेना आपको बताएगा कि संख्या 10 कितनी बार विभाजित होती है। असल में गुणा करना अधिक है।

संपादित करें: जुड़वां गिनती भी अधिक है, इसलिए आपको केवल मछलियों की आवश्यकता है।

और कुछ अजगर के लिए, मुझे लगता है कि यह काम करना चाहिए:

def countFives(n): 
    fives = 0 
    m = 5 
    while m <= n: 
     fives = fives + (n/m) 
     m = m*5 
    return fives 

Answer 3

आप बड़ी संख्या फ़ॉर्मेट करने के लिए एक DecimalFormat उपयोग कर सकते हैं। यदि आप अपना नंबर इस तरह प्रारूपित करते हैं तो आपको scientific notation में नंबर मिलता है तो प्रत्येक नंबर 1.4567E7 की तरह होगा जिससे यह आपके काम को अधिक आसान बना देगा। क्योंकि ई के बाद की संख्या - पीछे के पात्रों की संख्या। मुझे लगता है कि पिछली शून्यों की संख्या है।

मुझे नहीं पता कि यह आवश्यक सटीक पैटर्न है या नहीं। आप पैटर्न here

DecimalFormat formater = new DecimalFormat("0.###E0"); 

Answer 4

डबल प्रकार परिशुद्धता सीमित है के रूप में कैसे है, इसलिए यदि आप संख्या के साथ काम कर रहे हैं बहुत बड़ा डबल केवल एक सन्निकटन हो जाएगा मिल देख सकते हैं। इसके आस-पास काम करने के लिए आप बिगइन्टर जैसे कुछ मनमाने ढंग से बड़े पूर्णांक के लिए काम करने के लिए उपयोग कर सकते हैं।

Answer 5

जावा के युगल 9 * 10^18 से थोड़ा अधिक अधिकतम 25 पर! 1.5 * 10^25 है। यदि आप उच्च फैक्ट्रोरियल प्राप्त करने में सक्षम होना चाहते हैं तो आप बिगइन्टर का उपयोग करना चाहेंगे (बिगडिसीमल के समान लेकिन दशमलव नहीं करता है)।

Answer 6

मैंने इसे वास्तविक रूप से लिखा है, मुझे लगता है कि यह आपकी समस्या को सटीक रूप से हल करता है। मैंने बिगइंटर वर्ग का उपयोग उस कास्ट को डबल से पूर्णांक से बचने के लिए किया था, जो आपको समस्याएं पैदा कर सकता था। मैंने 25 से अधिक बड़ी संख्या में परीक्षण किया, जैसे कि 101, जो सटीक रूप से 24 शून्य लौटा।

विधि के पीछे विचार यह है कि यदि आप 25 लेते हैं! तो पहली गणना 25 * 24 = 600 है, इसलिए आप तुरंत दो शून्य बंद कर सकते हैं और फिर 6 * 23 = 138 कर सकते हैं। तो यह वास्तविक रूप से हटाने वाले शून्यों की गणना करता है।

public static int count(int number) { 
    final BigInteger zero = new BigInteger("0"); 
    final BigInteger ten = new BigInteger("10"); 
    int zeroCount = 0; 
    BigInteger mult = new BigInteger("1"); 
    while (number > 0) { 
     mult = mult.multiply(new BigInteger(Integer.toString(number))); 
     while (mult.mod(ten).compareTo(zero) == 0){ 
      mult = mult.divide(ten); 
      zeroCount += 1; 
     } 
     number -= 1; 
    } 
    return zeroCount; 
} 

जब से तुम ने कहा कि आप सभी पर चलाने के समय के बारे में परवाह नहीं है (न कि मेरी पहली विशेष रूप से प्रभावी है, बस थोड़ा और अधिक इसलिए था ताकि) इस एक बस भाज्य करता है और उसके बाद शून्य में गिना जाता है, तो यह cenceptually आसान है :

public static BigInteger factorial(int number) { 
    BigInteger ans = new BigInteger("1"); 
    while (number > 0) { 
     ans = ans.multiply(new BigInteger(Integer.toString(number))); 
     number -= 1; 
    } 
    return ans; 
} 

public static int countZeros(int number) { 
    final BigInteger zero = new BigInteger("0"); 
    final BigInteger ten = new BigInteger("10"); 
    BigInteger fact = factorial(number); 
    int zeroCount = 0; 
    while (fact.mod(ten).compareTo(zero) == 0){ 
     fact = fact.divide(ten); 
     zeroCount += 1; 
    } 
} 

Answer 7

मेरा 2 सेंट: त्रुटि-प्रवण होने के बाद से डबल के साथ काम करने से बचें। इस मामले में एक बेहतर डेटाप्रकार BigInteger है, और यहाँ वहाँ एक छोटा सा तरीका आपकी मदद करेगा:

public class CountTrailingZeroes { 

    public int countTrailingZeroes(double number) { 
     return countTrailingZeroes(String.format("%.0f", number)); 
    } 

    public int countTrailingZeroes(String number) { 
     int c = 0; 
     int i = number.length() - 1; 

     while (number.charAt(i) == '0') { 
      i--; 
      c++; 
     } 

     return c; 

    } 

    @Test 
    public void $128() { 
     assertEquals(0, countTrailingZeroes("128")); 
    } 

    @Test 
    public void $120() { 
     assertEquals(1, countTrailingZeroes("120")); 
    } 

    @Test 
    public void $1200() { 
     assertEquals(2, countTrailingZeroes("1200")); 
    } 

    @Test 
    public void $12000() { 
     assertEquals(3, countTrailingZeroes("12000")); 
    } 

    @Test 
    public void $120000() { 
     assertEquals(4, countTrailingZeroes("120000")); 
    } 

    @Test 
    public void $102350000() { 
     assertEquals(4, countTrailingZeroes("102350000")); 
    } 

    @Test 
    public void $1023500000() { 
     assertEquals(5, countTrailingZeroes(1023500000.0)); 
    } 
} 

Answer 8

यह मैं इसे कैसे किया जाता है, लेकिन साथ है बड़ा> 25 भाज्य लंबे क्षमता पर्याप्त नहीं है और चुड़ैल के साथ वर्ग Biginteger इस्तेमाल किया जाना चाहिए, मैं अभी तक परिचित नहीं हूँ :)

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    Scanner in = new Scanner(System.in); 
    System.out.print("Please enter a number : "); 
    long number = in.nextLong(); 
    long numFactorial = 1; 

    for(long i = 1; i <= number; i++) { 
     numFactorial *= i; 
    } 
    long result = 0; 
    int divider = 5; 
    for(divider =5; (numFactorial % divider) == 0; divider*=5) { 
     result += 1; 
    } 

    System.out.println("Factorial of n is: " + numFactorial); 
    System.out.println("The number contains " + result + " zeroes at its end."); 

    in.close(); 

} 

} 

Answer 9

के साथ सबसे अच्छा

लघुगणक समय जटिलता है निम्नलिखित:

public int trailingZeroes(int n) { 
    if (n < 0) 
     return -1; 

    int count = 0; 
    for (long i = 5; n/i >= 1; i *= 5) { 
     count += n/i; 
    } 

    return count; 
} 

बेशर्म से http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/

Answer 10

की नकल की मैं जावास्क्रिप्ट में हल करने के लिए एक ही मुद्दा था, और मैं रों इसे पसंद किया:

var number = 1000010000; 
var str = (number + '').split(''); //convert to string 
var i = str.length - 1; // start from the right side of the array 
var count = 0; //var where to leave result 
for (;i>0 && str[i] === '0';i--){ 
    count++; 
} 
console.log(count) // console shows 4 

यह समाधान आपको पिछली शून्यों की संख्या देता है।

var number = 1000010000; 
 
var str = (number + '').split(''); //convert to string 
 
var i = str.length - 1; // start from the right side of the \t array 
 
var count = 0; //var where to leave result 
 
for (;i>0 && str[i] === '0';i--){ 
 
\t count++; 
 
} 
 
console.log(count)