Trong bài viết này, chúng ta sẽ hiểu vấn đề tìm các số 0 ở cuối của một số N cho trước trong biểu diễn cơ số 16 của giai thừa của nó chẳng hạn
Input : N = 7 Output : 1 Explanation : fact(7) = 5040 in base10 and 13B0 in base16 having 1 trailing zero. Input : N = 11 Output : 2 Explanation : fact(11) = 39916800 in base10 and 2611500 in base16 having 2 trailing zeroes.
Trước tiên, hãy tóm tắt lại quá trình chuyển đổi bất kỳ số thập phân nào từ cơ số này sang cơ số khác; hãy lấy một ví dụ về chuyển đổi (5040) 10 thành (?) 16
tức là chia số cho 16 và giữ phần dư cho đến khi số đó không thể chia được nữa. Kết quả sẽ là phần còn lại theo thứ tự ngược lại.
Kết quả là chúng ta có một số 0 ở cuối và số 0 ở cuối này chúng ta nhận được khi 16 chia số có dư là 0.
Thừa số nguyên tố của 5040 =161 * 451 * 71, có nghĩa là 16 chia 5040 1 lần với dư 0, bằng các số 0 ở cuối. Bằng cách này, chúng ta có thể tính toán số lượng các số 0 ở cuối.
Phương pháp tiếp cận để tìm ra giải pháp
Chúng tôi đã thảo luận ở trên về cách tìm số lượng các số 0 ở cuối. Chúng ta cũng biết 16 =24, có nghĩa là lũy thừa cao nhất 2 trong N chia cho bốn sẽ bằng lũy thừa cao nhất của 16. Nó còn được gọi là công thức Legendre.
Mã C ++ cho cách tiếp cận trên
Đây là cú pháp C ++ mà chúng ta có thể sử dụng làm đầu vào để giải quyết vấn đề đã cho -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main () {
int n = 11;
long long int count = 0;
long long int value, power = 2;
long long int result;
do{
value = n / power;
count += value;
power *= 2;
}
while (value != 0);
// Count has the highest power of 2
result = count / 4;
cout << "Number of trailing zeroes in base 16 representation of N : " << result;
} Đầu ra
Number of trailing zeroes in base 16 representation of N: 2
Giải thích về đoạn mã trên
- Chúng tôi đang khởi tạo công suất bằng hai vì chúng tôi cần tính công suất cao nhất là 2.
- Triển khai công thức của Legendre trong vòng lặp while trong đó chúng ta chia n với lũy thừa, ban đầu là hai và số đếm tăng dần với giá trị và lũy thừa bằng 2.
- Sau khi chia lũy thừa cao nhất của 2 với 4 được lưu trong biến đếm.
- Cuối cùng, chúng tôi cũng đang in kết quả.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề tìm số lượng các số 0 ở cuối trong biểu diễn cơ số16 của giai thừa N, chúng tôi giải quyết vấn đề này bằng cách sử dụng công thức Legendre. Chúng tôi cũng viết mã C ++ để giải quyết vấn đề tương tự. Bạn có thể viết mã này bằng bất kỳ ngôn ngữ nào khác như Java, C, python, v.v. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.