Factorial Trailing Zeroes ການແກ້ໄຂບັນຫາ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Bloomberg
ຄະນິດສາດ

ຖະແຫຼງການບັນຫາ

ໃນປັນຫານີ້ພວກເຮົາຕ້ອງຊອກຮູ້ວ່າຈັກເລກສູນທີ່ຕິດຢູ່ຈະເປັນ ຈຳ ນວນເທົ່າໃດ n!
ມອບ n ເປັນການປ້ອນຂໍ້ມູນ.

ຄືກັບວ່າມີ ໜຶ່ງ ເລກສູນຢູ່ໃນ 5!
5! = 5 * 4 * 3 * 2 * 1 = 120

ຍົກຕົວຢ່າງ

n = 3
0

ຄຳ ອະທິບາຍ: 3! = 6, ບໍ່ມີເສັ້ນທາງສູນ

n = 0
0

ຄຳ ອະທິບາຍ: 0! = 1, ບໍ່ມີເສັ້ນທາງສູນ

 

ເພື່ອຊອກຫາ ຈຳ ນວນຂອງເລກສູນໃນ n! , ວິທີງ່າຍໆແມ່ນການຄິດໄລ່ n! ແລະກວດເບິ່ງວ່າມີຈັກສູນຢູ່ໃນຕອນທ້າຍ. ນີ້ພວກເຮົາສາມາດເຮັດໄດ້ງ່າຍໆໂດຍການກວດເບິ່ງວ່າແບ່ງ ຈຳ ນວນເລກ 10 ພວກເຮົາຈະໄດ້ເຫຼືອ 0 ແລະຫຼັງຈາກນັ້ນລົບເລກສູນສຸດທ້າຍໂດຍແບ່ງມັນອອກໂດຍ 10. ພວກເຮົາສາມາດນັບໄດ້ຈົນກວ່າພວກເຮົາຈະໄດ້ສ່ວນທີ່ເຫຼືອເທົ່າກັບສູນທຸກໆຄັ້ງ.

ແຕ່ວິທີການນີ້ບໍ່ແມ່ນພາກປະຕິບັດຕົວຈິງກັບຕົວເລກແບບງ່າຍດາຍເພາະວ່າພວກເຮົາຮູ້ n! ແມ່ນຕົວເລກໃຫຍ່ຫຼາຍ. ໃນຂະ ໜາດ C ++ ແລະ Java ແບບງ່າຍດາຍແມ່ນ 64-bit ທີ່ດີທີ່ສຸດເທົ່ານັ້ນທີ່ສາມາດເກັບຮັກສາເລກເຕັມພຽງແຕ່ຂອບເຂດ ຈຳ ກັດຂອງ 2 ^ 63 - 1. ເຊິ່ງປະມານ 10 ^ 18. ໃນພາສາຈາວາພວກເຮົາສາມາດໃຊ້ຫ້ອງຮຽນ BigInteger ເພື່ອເກັບຮັກສາຕົວເລກໃຫຍ່ໆເຊັ່ນ: n !. ແຕ່ວິທີການບັງຄັບໃຊ້ຂອງສັດນີ້ມີເວລາໃຫຍ່ແລະມີຄວາມສັບສົນໃນອະວະກາດ.

ໃນທີ່ນີ້ພວກເຮົາຈະປຶກສາຫາລືກ່ຽວກັບວິທີແກ້ໄຂທີ່ມີປະສິດທິພາບ ສຳ ລັບການຊອກຫາເລກສູນໃນ n!

ວິທີການ 1 (ປັດໃຈຄິດໄລ່ຂອງ 5)

ພວກເຮົາສາມາດເວົ້າໄດ້ວ່າ ຈຳ ນວນເລກສູນທັງ ໝົດ ທີ່ຕິດຕາມມາຈະເທົ່າກັບ ຈຳ ນວນເທົ່າໃດ 10 ແມ່ນປັດໃຈຂອງຕົວເລກນັ້ນ. ແລະພວກເຮົາຮູ້ວ່າທຸກໆ 10 ຖືກສ້າງຕັ້ງຂຶ້ນຈາກຜະລິດຕະພັນຂອງສອງຕົວເລກ 2 ແລະ 5.
ສະນັ້ນຖ້າພວກເຮົາຊອກຮູ້ວ່າມີ 2 ປັດໃຈຂອງ 5 ໃນ ຈຳ ນວນນັ້ນມີ ຈຳ ນວນເທົ່າໃດ. ຄ້າຍຄືກັນວ່າມີຫລາຍປັດໃຈຂອງ 10 ໃນນັ້ນ. ຈາກນັ້ນພວກເຮົາສາມາດເວົ້າໄດ້ວ່າແຕ່ລະອັນນີ້ຈະລວມກັນເພື່ອເຮັດໃຫ້ຜະລິດຕະພັນເທົ່າກັບ 2. ສະນັ້ນ ຈຳ ນວນທັງ ໝົດ ຂອງເສັ້ນທາງສູນຈະເທົ່າກັບຕ່ ຳ ສຸດ (ນັບ 5, ນັບ XNUMX ຂອງ).

ດຽວນີ້ພວກເຮົາຕ້ອງນັບປັດໃຈເຫລົ່ານີ້ໃນ n!.
ນ! = 1 * 2 * 3 … .. * (n-1) * ນ

ດັ່ງນັ້ນພວກເຮົາຈະປັບຕົວເລກທັງ ໝົດ ຈາກ 2 ຫາ n (ເພີ່ມຂື້ນ 2 ໂດຍພວກມັນແມ່ນຕົວເລກທີ່ມີຢ່າງ ໜ້ອຍ 2 ຕົວ).
ສຳ ລັບແຕ່ລະຕົວເລກພວກເຮົາຈະແບ່ງມັນເທື່ອລະ 2 ເທື່ອຈົນກວ່າມັນຈະສາມາດແບ່ງອອກໂດຍ 2 ເພື່ອຊອກຫາການນັບ ຈຳ ນວນ 2 ໃນການ ນຳ ເອົາປັດໃຈຂອງ ຈຳ ນວນນັ້ນໄປ.
ຄ້າຍຄືກັນເພື່ອຊອກຫາຕົວເລກຂອງ 5 ໃນ ຈຳ ນວນນັ້ນພວກເຮົາຈະເຮັດຄືກັນ.
ໃນປັດຈຸບັນພວກເຮົາຈະກັບຄືນຕໍາ່ສຸດທີ່ສອງໃນສອງການນັບນີ້.

ສິ່ງນີ້ເຮັດວຽກໄດ້ແຕ່ພວກເຮົາຍັງສາມາດເພີ່ມປະສິດທິພາບມັນໄດ້ເລັກ ໜ້ອຍ. ພວກເຮົາສາມາດວິເຄາະໄດ້ວ່າພວກເຮົາມີຕົວເລກຕັ້ງແຕ່ 1 ເຖິງ n, ສະນັ້ນພວກເຮົາຈະໄດ້ຮັບ ອຳ ນາດ 2 ຈາກ ຈຳ ນວນ ອຳ ນາດເກີນ 5.
ເຊັ່ນດຽວກັນຈົນເຖິງ 4 ພວກເຮົາຈະໄດ້ຮັບສອງຕົວເລກທີ່ມີ 2 ເປັນປັດໃຈ (2 ແລະ 4). ຢູ່ທີ່ 5 ພວກເຮົາໄດ້ຮັບເລກ ທຳ ອິດທີ່ມີ 5 ເປັນປັດໃຈ. ສະນັ້ນສິ່ງນີ້ຈະ ດຳ ເນີນຕໍ່ໄປພ້ອມກັບຄວາມແຕກຕ່າງ (ນັບ) ທີ່ຄ້າຍຄືກັນ. ນີ້ແມ່ນການເບິ່ງເຫັນທີ່ສະແດງໃຫ້ເຫັນວ່າຄວາມ ໜາ ແໜ້ນ ລະຫວ່າງ 2 ປັດໃຈແລະ 5 ປັດໃຈແຕກຕ່າງກັນແນວໃດ.

Factorial Trailing Zeroes ການແກ້ໄຂບັນຫາ Leetcode

ເພາະສະນັ້ນພວກເຮົາສາມາດສະຫຼຸບໄດ້ວ່າການນັບ 2 ແມ່ນສະເຫມີໃຫຍ່ກວ່າ ຈຳ ນວນ 5 ໃນ n!.
ດັ່ງນັ້ນພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາ ຈຳ ນວນ 5 ອັນເທົ່ານັ້ນແລະນັ້ນຈະເປັນ ຄຳ ຕອບ. ວິທີນີ້ພວກເຮົາຫຼຸດ ໜ້າ ວຽກລົງເຄິ່ງ ໜຶ່ງ.

ການຈັດຕັ້ງປະຕິບັດເພື່ອການແກ້ໄຂ Factorial Trailing Zeroes Leetcode Solution

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    for(int i=5;i<=n;i+=5)
    {
        int x=i;
        while(x>0 && x%5==0)
        {
            ++fives;
            x/=5;
        }
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

Java Program

class Rextester{
    
    public static int trailingZeroes(int n) 
    {
        int fives=0;
        for(int i=5;i<=n;i+=5)
        {
            int x=i;
            while(x>0 && x%5==0)
            {
                ++fives;
                x/=5;
            }
        }
        return fives;
    }
    
  public static void main(String args[])
    {    	
    System.out.println(trailingZeroes(5));
    }
}
1

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການແກ້ໄຂຄວາມຈິງຂອງການຄົ້ນຫາຄວາມຈິງ Leetcode

ຄວາມສັບສົນເວລາ

ໂອ (n): ພວກເຮົາກໍາລັງ iterating ຫຼາຍກວ່າຄູນທັງຫມົດຂອງຫ້າ till n. ມັນອາດຈະເບິ່ງຄືວ່າ ສຳ ລັບແຕ່ລະອົງປະກອບທີ່ພວກເຮົາ ກຳ ລັງໃຊ້ເວລາເພື່ອຊອກຫາ ຈຳ ນວນຫ້າ. ແຕ່ວ່າມັນໄດ້ແບ່ງສ່ວນໃຫ້ O (1) ເພາະວ່າຕົວເລກສ່ວນໃຫຍ່ທີ່ພວກເຮົາໄດ້ກວດກາມີພຽງແຕ່ປັດໃຈດຽວຂອງຫ້າ. ສະນັ້ນຄວາມສັບສົນທັງ ໝົດ ຂອງເວລາຍັງຄົງເປັນ O (n).

ຄວາມສັບສົນໃນອະວະກາດ 

O (1): ບໍ່ມີຄວາມ ຈຳ ພິເສດຫຍັງໃຊ້.

ວິທີທີ່ 2 (ປັດໃຈນັບ 5 ຢ່າງມີປະສິດທິພາບ)

ໃນວິທີການຂ້າງເທິງນີ້ພວກເຮົາໄດ້ເຫັນວ່າພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາ ຈຳ ນວນ 5 ອັນທີ່ເປັນປັດໃຈຂອງ n!. ໃນວິທີການຂ້າງເທິງນີ້ພວກເຮົາໄດ້ລວບລວມຕົວຄູນທັງ ໝົດ ຂອງ 5 ແລະເພີ່ມ ຈຳ ນວນ 5 ຂອງແຕ່ລະຕົວເລກແລະໄດ້ຮັບ ຄຳ ຕອບຂອງພວກເຮົາໃນເວລາເສັ້ນ. ພວກເຮົາຈະເຮັດການສັງເກດຂັ້ນສຸດທ້າຍເຊິ່ງຈະຊ່ວຍໃຫ້ພວກເຮົາສາມາດຄິດໄລ່ ຄຳ ຕອບໃນເວລາ logarithmic.

ໃນ n! (ຕົວຢ່າງຈາກ 1 ເຖິງ n) ພວກເຮົາມີບາງຕົວເລກທີ່ບໍ່ສາມາດແບ່ງປັນໄດ້ໂດຍ 5 (ປະກອບສ່ວນ 0 ສຳ ລັບການນັບ 5), ຫຼັງຈາກນັ້ນພວກເຮົາມີບາງຕົວເລກທີ່ສາມາດແບ່ງອອກເປັນ 5 (ແຕ່ລະສ່ວນປະກອບ ໜຶ່ງ ນັບ), ຫຼັງຈາກນັ້ນພວກເຮົາມີຕົວເລກທີ່ສາມາດແບ່ງອອກໂດຍ 25 (ເທື່ອນີ້ມີການປະກອບສ່ວນພິເສດຈາກ ຈຳ ນວນຫລາຍຕົວເລກເຫລົ່ານີ້), ແລ້ວແບ່ງອອກໂດຍ 125 (ການປະກອບສ່ວນພິເສດຈາກ ຈຳ ນວນເຫລົ່ານີ້), ເຊັ່ນນີ້ແລະອື່ນໆ.

ຫຼັງຈາກນັ້ນ ຄຳ ຕອບຂອງພວກເຮົາຈະເປັນຜົນລວມຂອງການປະກອບສ່ວນທັງ ໝົດ ນີ້.
ພວກເຮົາສາມາດສະຫຼຸບໄດ້ທັງ ໝົດ ດັ່ງລຸ່ມນີ້:
ຈຳ ນວນທັງ ໝົດ 5 ຂອງ = n / 5 + n / 25 + n / 125 + …. ອື່ນໆ
ນີ້ຈະໄປຈົນກ່ວາຕົວຫານແມ່ນ ໜ້ອຍ ກ່ວາ n ເພາະວ່າຫຼັງຈາກນັ້ນມູນຄ່າລວມຂອງສ່ວນ ໜຶ່ງ ຈະເປັນສູນ.

ຂັ້ນຕອນ:
ເລີ່ມຕົ້ນຕົວປ່ຽນຕົວຫານກັບ 5.
Run a loop, ໃນແຕ່ລະ iteration ເພີ່ມມູນຄ່າ n / ຕົວເລກໃຫ້ຜົນແລະຄູນຕົວຫານໂດຍ 5. ດຳ ເນີນການ loop ຈົນກ່ວາຕົວຫານ <n.

ການຈັດຕັ້ງປະຕິບັດເພື່ອການແກ້ໄຂ Factorial Trailing Zeroes Leetcode Solution

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    int den=5;

    while(den <= n)
    {
       fives += n/den;
       den *= 5;
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

Java Program

#include <bits/stdc++.h>
using namespace std;

int trailingZeroes(int n) 
{
    int fives=0;
    int den=5;

    while(den <= n)
    {
       fives += n/den;
       den *= 5;
    }
    return fives;
}

int main() 
{
   cout<<trailingZeroes(5)<<endl;
   return 0; 
}
1

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການແກ້ໄຂຄວາມຈິງຂອງການຄົ້ນຫາຄວາມຈິງ Leetcode

ຄວາມສັບສົນເວລາ

O (log (n)): ພວກເຮົາ ກຳ ລັງຄູນຕົວຫານໂດຍ 5 ແຕ່ລະຄັ້ງຈົນກວ່າມັນຈະນ້ອຍກວ່າ n. ເພາະສະນັ້ນ ຈຳ ນວນການອອກສຽງທັງ ໝົດ ຈະຖືກບັນທຶກ (n).

ຄວາມສັບສົນໃນອະວະກາດ 

O (1): ບໍ່ມີຄວາມ ຈຳ ພິເສດຫຍັງໃຊ້.