50. Pow(x, n)
Tags:
Medium
Skills:
Math
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tính x^n với x là số thực và n là số nguyên (có thể âm, dương hoặc 0)
Approach - Binary exponentiation with iterative
Dựa vào biểu diễn nhị phân của n, mỗi bit 1 sẽ nhân thêm một lũy thừa tương ứng
- Nếu n âm, chuyển x thành 1/x và n thành -n
- Dùng biến res để tích lũy kết quả
- Mỗi lần lặp, nếu n lẻ thì nhân res với curr_product
- Luôn bình phương curr_product và chia đôi n đến khi n = 0
Solution
typescripttypescript
1function myPow(x: number, n: number): number {
2 let N = n;
3 if(N < 0) {
4 x = 1 / x;
5 N = -N
6 }
7
8 let res = 1;
9 let curr_product = x;
10 while(N > 0) {
11 if(N % 2 === 1) res *= curr_product;
12 curr_product *= curr_product;
13 N = Math.floor(N / 2)
14 }
15 return res;
16};💡
Biểu diễn nhị phân?
- Mọi số nguyên dương n đều có thể viết dưới dạng số nhị phân, tức là chỉ dùng các chữ số 0 và 1
- Ví dụ: n=13 có nhị phân là 1101, tức là 13=8+4+1=2^3+2^2+2^0
Ứng dụng vào tính lũy thừa
→ Với mỗi bit 1 trong nhị phân của n, ta sẽ nhân thêm một lũy thừa tương ứng của x
Giải thích chi tiết
- Trong biểu diễn nhị phân, mỗi bit 1 của số mũ N đại diện cho một lũy thừa của 2 mà bạn cần nhân vào kết quả cuối cùng
- Nếu bit hiện tại là 1 (N lẻ), bạn nhân res với curr_product vì nó đóng góp vào tổng số mũ.
- Nếu bit hiện tại là 0 (N chẵn), bạn không nhân res với curr_product vì lũy thừa tương ứng với bit này không xuất hiện trong tổng số mũ cần tính