Products excluding each element of the array
$begingroup$
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Is there a better solution for this problem?
Note: Division is not allowed.
public class DailyCodingProblem2 {
public static void main(String args) {
int arr = { 1, 2, 3, 4, 5 };
int ans = solution(arr, arr.length);
System.out.println(Arrays.toString(ans));
arr = new int { 3, 2, 1 };
ans = solution(arr, arr.length);
System.out.println(Arrays.toString(ans));
}
private static int solution(int arr, int n) {
int left = new int[n];
int right = new int[n];
int res = new int[n];
left[0] = 1;
right[n - 1] = 1;
for (int i = 1; i < n; i++) {
left[i] = arr[i - 1] * left[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
right[i] = arr[i + 1] * right[i + 1];
}
for (int i = 0; i < n; i++) {
res[i] = left[i] * right[i];
}
return res;
}
}
java algorithm array
edited 6 mins ago
Solomon Ucko
1,112415
asked 2 days ago
Maclean PintoMaclean Pinto
1225
$endgroup$
add a comment |
$begingroup$
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Is there a better solution for this problem?
Note: Division is not allowed.
public class DailyCodingProblem2 {
public static void main(String args) {
int arr = { 1, 2, 3, 4, 5 };
int ans = solution(arr, arr.length);
System.out.println(Arrays.toString(ans));
arr = new int { 3, 2, 1 };
ans = solution(arr, arr.length);
System.out.println(Arrays.toString(ans));
}
private static int solution(int arr, int n) {
int left = new int[n];
int right = new int[n];
int res = new int[n];
left[0] = 1;
right[n - 1] = 1;
for (int i = 1; i < n; i++) {
left[i] = arr[i - 1] * left[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
right[i] = arr[i + 1] * right[i + 1];
}
for (int i = 0; i < n; i++) {
res[i] = left[i] * right[i];
}
return res;
}
}
java algorithm array
edited 6 mins ago
Solomon Ucko
1,112415
asked 2 days ago
Maclean PintoMaclean Pinto
1225
$endgroup$
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Mast
2 days ago
$begingroup$
"Note: Division is not allowed." Why? Is it because of a restriction for the assignment?
$endgroup$
– Solomon Ucko
2 days ago
$begingroup$
@SolomonUcko Yes it is a restriction for the assignment
$endgroup$
– Maclean Pinto
6 mins ago
add a comment |
$begingroup$
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Is there a better solution for this problem?
Note: Division is not allowed.
public class DailyCodingProblem2 {
public static void main(String args) {
int arr = { 1, 2, 3, 4, 5 };
int ans = solution(arr, arr.length);
System.out.println(Arrays.toString(ans));
arr = new int { 3, 2, 1 };
ans = solution(arr, arr.length);
System.out.println(Arrays.toString(ans));
}
private static int solution(int arr, int n) {
int left = new int[n];
int right = new int[n];
int res = new int[n];
left[0] = 1;
right[n - 1] = 1;
for (int i = 1; i < n; i++) {
left[i] = arr[i - 1] * left[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
right[i] = arr[i + 1] * right[i + 1];
}
for (int i = 0; i < n; i++) {
res[i] = left[i] * right[i];
}
return res;
}
}
java algorithm array
edited 6 mins ago
Solomon Ucko
1,112415
asked 2 days ago
Maclean PintoMaclean Pinto
1225
$endgroup$
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Is there a better solution for this problem?
Note: Division is not allowed.
public class DailyCodingProblem2 {
public static void main(String args) {
int arr = { 1, 2, 3, 4, 5 };
int ans = solution(arr, arr.length);
System.out.println(Arrays.toString(ans));
arr = new int { 3, 2, 1 };
ans = solution(arr, arr.length);
System.out.println(Arrays.toString(ans));
}
private static int solution(int arr, int n) {
int left = new int[n];
int right = new int[n];
int res = new int[n];
left[0] = 1;
right[n - 1] = 1;
for (int i = 1; i < n; i++) {
left[i] = arr[i - 1] * left[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
right[i] = arr[i + 1] * right[i + 1];
}
for (int i = 0; i < n; i++) {
res[i] = left[i] * right[i];
}
return res;
}
}
java algorithm array
java algorithm array
edited 6 mins ago
Solomon Ucko
1,112415
asked 2 days ago
Maclean PintoMaclean Pinto
1225
edited 6 mins ago
Solomon Ucko
1,112415
asked 2 days ago
Maclean PintoMaclean Pinto
1225
edited 6 mins ago
Solomon Ucko
1,112415
edited 6 mins ago
Solomon Ucko
1,112415
edited 6 mins ago
Solomon Ucko
1,112415
1,112415
asked 2 days ago
Maclean PintoMaclean Pinto
1225
asked 2 days ago
Maclean PintoMaclean Pinto
1225
asked 2 days ago
Maclean PintoMaclean Pinto
1225
1225
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Mast
2 days ago
$begingroup$
"Note: Division is not allowed." Why? Is it because of a restriction for the assignment?
$endgroup$
– Solomon Ucko
2 days ago
$begingroup$
@SolomonUcko Yes it is a restriction for the assignment
$endgroup$
– Maclean Pinto
6 mins ago
add a comment |
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Mast
2 days ago
$begingroup$
"Note: Division is not allowed." Why? Is it because of a restriction for the assignment?
$endgroup$
– Solomon Ucko
2 days ago
$begingroup$
@SolomonUcko Yes it is a restriction for the assignment
$endgroup$
– Maclean Pinto
6 mins ago
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Mast
2 days ago
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Mast
2 days ago
$begingroup$
"Note: Division is not allowed." Why? Is it because of a restriction for the assignment?
$endgroup$
– Solomon Ucko
2 days ago
$begingroup$
"Note: Division is not allowed." Why? Is it because of a restriction for the assignment?
$endgroup$
– Solomon Ucko
2 days ago
$begingroup$
@SolomonUcko Yes it is a restriction for the assignment
$endgroup$
– Maclean Pinto
6 mins ago
$begingroup$
@SolomonUcko Yes it is a restriction for the assignment
$endgroup$
– Maclean Pinto
6 mins ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Time complexity-wise, I think not. You're required to 'visit' all numbers, and your solution is O(n), so that can't be improved.
Code clarity could be improved, as it's not very obvious what the intention is. Some comments would help that.
I think shifting indices by 1 might make it clearer (left[i+1] = arr[i] * left[i]), but then maybe not because it'd mess up the last loop.
Have you explored different algorithms? I wonder if straightforward memoization makes a very clear solution for this.
answered 2 days ago
domendomen
1762
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f212674%2fproducts-excluding-each-element-of-the-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Time complexity-wise, I think not. You're required to 'visit' all numbers, and your solution is O(n), so that can't be improved.
Code clarity could be improved, as it's not very obvious what the intention is. Some comments would help that.
I think shifting indices by 1 might make it clearer (left[i+1] = arr[i] * left[i]), but then maybe not because it'd mess up the last loop.
Have you explored different algorithms? I wonder if straightforward memoization makes a very clear solution for this.
answered 2 days ago
domendomen
1762
$endgroup$
add a comment |
$begingroup$
Time complexity-wise, I think not. You're required to 'visit' all numbers, and your solution is O(n), so that can't be improved.
Code clarity could be improved, as it's not very obvious what the intention is. Some comments would help that.
I think shifting indices by 1 might make it clearer (left[i+1] = arr[i] * left[i]), but then maybe not because it'd mess up the last loop.
Have you explored different algorithms? I wonder if straightforward memoization makes a very clear solution for this.
answered 2 days ago
domendomen
1762
$endgroup$
add a comment |
$begingroup$
Time complexity-wise, I think not. You're required to 'visit' all numbers, and your solution is O(n), so that can't be improved.
Code clarity could be improved, as it's not very obvious what the intention is. Some comments would help that.
I think shifting indices by 1 might make it clearer (left[i+1] = arr[i] * left[i]), but then maybe not because it'd mess up the last loop.
Have you explored different algorithms? I wonder if straightforward memoization makes a very clear solution for this.
answered 2 days ago
domendomen
1762
$endgroup$
Time complexity-wise, I think not. You're required to 'visit' all numbers, and your solution is O(n), so that can't be improved.
Code clarity could be improved, as it's not very obvious what the intention is. Some comments would help that.
I think shifting indices by 1 might make it clearer (left[i+1] = arr[i] * left[i]), but then maybe not because it'd mess up the last loop.
Have you explored different algorithms? I wonder if straightforward memoization makes a very clear solution for this.
answered 2 days ago
domendomen
1762
answered 2 days ago
domendomen
1762
answered 2 days ago
domendomen
1762
answered 2 days ago
domendomen
1762
1762
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f212674%2fproducts-excluding-each-element-of-the-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
$endgroup$
– Mast
2 days ago
$begingroup$
"Note: Division is not allowed." Why? Is it because of a restriction for the assignment?
$endgroup$
– Solomon Ucko
2 days ago
$begingroup$
@SolomonUcko Yes it is a restriction for the assignment
$endgroup$
– Maclean Pinto
6 mins ago