英文:
Pascal Triangle Integer Overflow when values need to be find at row 30
问题
这是整数溢出问题，但我无法理解如何仅使用整数解决它，而不使用长整数。我想知道在溢出发生时如何测试或形成方程，而不转向更高的数据类型。
目标：尝试找到帕斯卡三角形中第i个索引的值；
rowIndex 可以最大为33。
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> pt = new ArrayList<>();
int prev = 1;
int curr = 1;
int n = rowIndex + 1;
pt.add(prev);
for (int i = 1; i <= rowIndex; i++) {
curr = prev * (n - i) / i;
pt.add(curr);
prev = curr;
}
return pt;
}
}
英文:
This is Integer overflow problem but i am not able to wrap my head around it for using only Integer for solution [not using long ].
I want to know how can we test or form equation when overflow happens without moving to higher datatype?
Aim : try to find pascal triangle values at i index ;
rowIndex can be max 33.
Code:
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> pt = new ArrayList<>();
int prev=1;
int curr=1;
int n=rowIndex+1;
pt.add(prev);
for (int i=1; i <= rowIndex; i++) {
curr = prev * (n-i)/i;
pt.add(curr);
prev=curr;
}
return pt;
}
答案1
得分: 1
你可以通过使用long而不是int来防止溢出。
public List<Integer> getRow(int rowIndex) {
List<Integer> pt = new ArrayList<>();
int prev = 1;
int curr = 1;
int n = rowIndex + 1;
pt.add(prev);
for (int i = 1; i <= rowIndex; i++) {
curr = (int) ((long) prev * (n - i) / i);
pt.add(curr);
prev = curr;
}
return pt;
}
但是，可以在不使用long的情况下解决这个问题。prev * (n - i) 部分可能会溢出，但这个乘积应该能被i整除。您可以通过在乘法之前进行除法来避免溢出。如果提前计算(n - i)和i的最大公约数 (GCD)，则可以按以下方式重写。
int gcd = gcd(n - i, i);
curr = (prev / (i / gcd)) * ((n - i) / gcd);
GCD可以通过以下方法获得。
static int gcd(int m, int n) {
while (n > 0) {
int r = m % n;
m = n;
n = r;
}
return m;
}
在之前：
[1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, -131213633, -123012780, -101304642, -73164463, -46209134, -25415023, -12102391, -4950978, -1722079, -502273, -120545, -23181, -3434, -367, -25, 0]
之后：
[1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, 155117520, 145422675, 119759850, 86493225, 54627300, 30045015, 14307150, 5852925, 2035800, 593775, 142506, 27405, 4060, 435, 30, 1]
英文:
You can prevent overflow by using long instead of int.
public List<Integer> getRow(int rowIndex) {
List<Integer> pt = new ArrayList<>();
int prev=1;
int curr=1;
int n=rowIndex+1;
pt.add(prev);
for (int i=1; i <= rowIndex; i++) {
curr = (int) ((long) prev * (n-i)/i);
pt.add(curr);
prev=curr;
}
return pt;
}
But the problem can be solved without using long.
The prev * (n-i) part may overflow, but this product should be divisible by i. You can avoid the overflow by dividing before the multiplication. If you calculate GCD of (n-i) and i in advance, you can rewrite as follows.
int gcd = gcd(n - i, i);
curr = (prev / (i / gcd)) * ((n - i) / gcd);
GCD can be obtained by the following method.
static int gcd(int m, int n) {
while (n > 0) {
int r = m % n;
m = n;
n = r;
}
return m;
}
before:
[1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, -131213633, -123012780, -101304642, -73164463, -46209134, -25415023, -12102391, -4950978, -1722079, -502273, -120545, -23181, -3434, -367, -25, 0]
after:
[1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, 155117520, 145422675, 119759850, 86493225, 54627300, 30045015, 14307150, 5852925, 2035800, 593775, 142506, 27405, 4060, 435, 30, 1]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论