首页 > 代码库 > Multiplication of numbers
Multiplication of numbers
Questin:
There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. Solve it without division operator and in O(n).
For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
Example:
A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}
思路:
可以使用迭代累计。把output[i]=a[i]左边的乘积 x a[i]右边的乘积,所以,我们可以分两个循环,第一次先把A[i]左边的乘积放在Output[i]中,第二次把A[i]右边的乘积算出来;也可以直接放在一个循环中,只不过需要同时计算左边的乘积和右边的乘积。
代码如下:
void Multiplication_Array(int A[], int OUTPUT[], int n) { int left = 1; int right = 1; for (int i = 0; i < n; i++) OUTPUT[i] = 1; for (int i = 0; i < n; i++) { OUTPUT[i] *= left; OUTPUT[n - 1 - i] *= right; left *= A[i]; right *= A[n - 1 - i]; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。