Codility “PermMissingElem” Solution
$begingroup$
This is my solution to the PermMissingElem problem, I wonder what can be improved? Expected worst case time complexity is O(N), but the performance test shows that it's O(N) or O(N * log(N)), which I suppose there's some solution out there that can truly achieve pure O(N)?
function solution(A) {
const size = A.length;
let sum = 0;
for (i=0;i<size;i++){
sum += A[i];
}
return (((size+ 1)*(size + 2))/2) - sum
}
The original problem is quoted as follows:
A zero-indexed array A consisting of N different integers is given.
The array contains integers in the range [1..(N + 1)], which means
that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
int solution(int A, int N); that, given a zero-indexed array A,
returns the value of the missing element.
For example, given array A such that:
A[0] = 2 A1 = 3 A[2] = 1 A[3] = 5 the function should return
4, as it is the missing element.
Assume that:
N is an integer within the range [0..100,000]; the elements of A are
all distinct; each element of array A is an integer within the range
[1..(N + 1)].
Complexity:
expected worst-case time complexity is O(N); expected worst-case space
complexity is O(1), beyond input storage (not counting the storage
required for input arguments). Elements of input arrays can be
modified.
javascript programming-challenge bitwise
asked Jun 7 '17 at 19:25
kdenzkdenz
1888
$endgroup$
add a comment |
$begingroup$
This is my solution to the PermMissingElem problem, I wonder what can be improved? Expected worst case time complexity is O(N), but the performance test shows that it's O(N) or O(N * log(N)), which I suppose there's some solution out there that can truly achieve pure O(N)?
function solution(A) {
const size = A.length;
let sum = 0;
for (i=0;i<size;i++){
sum += A[i];
}
return (((size+ 1)*(size + 2))/2) - sum
}
The original problem is quoted as follows:
A zero-indexed array A consisting of N different integers is given.
The array contains integers in the range [1..(N + 1)], which means
that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
int solution(int A, int N); that, given a zero-indexed array A,
returns the value of the missing element.
For example, given array A such that:
A[0] = 2 A1 = 3 A[2] = 1 A[3] = 5 the function should return
4, as it is the missing element.
Assume that:
N is an integer within the range [0..100,000]; the elements of A are
all distinct; each element of array A is an integer within the range
[1..(N + 1)].
Complexity:
expected worst-case time complexity is O(N); expected worst-case space
complexity is O(1), beyond input storage (not counting the storage
required for input arguments). Elements of input arrays can be
modified.
javascript programming-challenge bitwise
asked Jun 7 '17 at 19:25
kdenzkdenz
1888
$endgroup$
1
$begingroup$
Have you looked at this related question?
$endgroup$
– yuri
Jun 7 '17 at 20:26
$begingroup$
Can you share a performance test which reveals $O(Nlog{N})$ complexity?
$endgroup$
– vnp
Jun 8 '17 at 1:52
$begingroup$
Just a note for people who may wonder at how the solution was arrived at. When you read the corresponding material at codility.com/media/train/1-TimeComplexity.pdf, accessed via app.codility.com/programmers/lessons/3-time_complexity, it explains the optimal solution for finding the sum of integers 1..N. This solution can be applied to this problem, since we can find the sum of integers 1..N+1, and then subtract the sum of the integers in the array, in order to find the missing integer in the array.
$endgroup$
– James Ray
46 mins ago
add a comment |
$begingroup$
This is my solution to the PermMissingElem problem, I wonder what can be improved? Expected worst case time complexity is O(N), but the performance test shows that it's O(N) or O(N * log(N)), which I suppose there's some solution out there that can truly achieve pure O(N)?
function solution(A) {
const size = A.length;
let sum = 0;
for (i=0;i<size;i++){
sum += A[i];
}
return (((size+ 1)*(size + 2))/2) - sum
}
The original problem is quoted as follows:
A zero-indexed array A consisting of N different integers is given.
The array contains integers in the range [1..(N + 1)], which means
that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
int solution(int A, int N); that, given a zero-indexed array A,
returns the value of the missing element.
For example, given array A such that:
A[0] = 2 A1 = 3 A[2] = 1 A[3] = 5 the function should return
4, as it is the missing element.
Assume that:
N is an integer within the range [0..100,000]; the elements of A are
all distinct; each element of array A is an integer within the range
[1..(N + 1)].
Complexity:
expected worst-case time complexity is O(N); expected worst-case space
complexity is O(1), beyond input storage (not counting the storage
required for input arguments). Elements of input arrays can be
modified.
javascript programming-challenge bitwise
asked Jun 7 '17 at 19:25
kdenzkdenz
1888
$endgroup$
This is my solution to the PermMissingElem problem, I wonder what can be improved? Expected worst case time complexity is O(N), but the performance test shows that it's O(N) or O(N * log(N)), which I suppose there's some solution out there that can truly achieve pure O(N)?
function solution(A) {
const size = A.length;
let sum = 0;
for (i=0;i<size;i++){
sum += A[i];
}
return (((size+ 1)*(size + 2))/2) - sum
}
The original problem is quoted as follows:
A zero-indexed array A consisting of N different integers is given.
The array contains integers in the range [1..(N + 1)], which means
that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
int solution(int A, int N); that, given a zero-indexed array A,
returns the value of the missing element.
For example, given array A such that:
A[0] = 2 A1 = 3 A[2] = 1 A[3] = 5 the function should return
4, as it is the missing element.
Assume that:
N is an integer within the range [0..100,000]; the elements of A are
all distinct; each element of array A is an integer within the range
[1..(N + 1)].
Complexity:
expected worst-case time complexity is O(N); expected worst-case space
complexity is O(1), beyond input storage (not counting the storage
required for input arguments). Elements of input arrays can be
modified.
javascript programming-challenge bitwise
javascript programming-challenge bitwise
asked Jun 7 '17 at 19:25
kdenzkdenz
1888
asked Jun 7 '17 at 19:25
kdenzkdenz
1888
asked Jun 7 '17 at 19:25
kdenzkdenz
1888
asked Jun 7 '17 at 19:25
kdenzkdenz
1888
asked Jun 7 '17 at 19:25
kdenzkdenz
1888
1888
1
$begingroup$
Have you looked at this related question?
$endgroup$
– yuri
Jun 7 '17 at 20:26
$begingroup$
Can you share a performance test which reveals $O(Nlog{N})$ complexity?
$endgroup$
– vnp
Jun 8 '17 at 1:52
$begingroup$
Just a note for people who may wonder at how the solution was arrived at. When you read the corresponding material at codility.com/media/train/1-TimeComplexity.pdf, accessed via app.codility.com/programmers/lessons/3-time_complexity, it explains the optimal solution for finding the sum of integers 1..N. This solution can be applied to this problem, since we can find the sum of integers 1..N+1, and then subtract the sum of the integers in the array, in order to find the missing integer in the array.
$endgroup$
– James Ray
46 mins ago
add a comment |
1
$begingroup$
Have you looked at this related question?
$endgroup$
– yuri
Jun 7 '17 at 20:26
$begingroup$
Can you share a performance test which reveals $O(Nlog{N})$ complexity?
$endgroup$
– vnp
Jun 8 '17 at 1:52
$begingroup$
Just a note for people who may wonder at how the solution was arrived at. When you read the corresponding material at codility.com/media/train/1-TimeComplexity.pdf, accessed via app.codility.com/programmers/lessons/3-time_complexity, it explains the optimal solution for finding the sum of integers 1..N. This solution can be applied to this problem, since we can find the sum of integers 1..N+1, and then subtract the sum of the integers in the array, in order to find the missing integer in the array.
$endgroup$
– James Ray
46 mins ago
1
1
$begingroup$
Have you looked at this related question?
$endgroup$
– yuri
Jun 7 '17 at 20:26
$begingroup$
Have you looked at this related question?
$endgroup$
– yuri
Jun 7 '17 at 20:26
$begingroup$
Can you share a performance test which reveals $O(Nlog{N})$ complexity?
$endgroup$
– vnp
Jun 8 '17 at 1:52
$begingroup$
Can you share a performance test which reveals $O(Nlog{N})$ complexity?
$endgroup$
– vnp
Jun 8 '17 at 1:52
$begingroup$
Just a note for people who may wonder at how the solution was arrived at. When you read the corresponding material at codility.com/media/train/1-TimeComplexity.pdf, accessed via app.codility.com/programmers/lessons/3-time_complexity, it explains the optimal solution for finding the sum of integers 1..N. This solution can be applied to this problem, since we can find the sum of integers 1..N+1, and then subtract the sum of the integers in the array, in order to find the missing integer in the array.
$endgroup$
– James Ray
46 mins ago
$begingroup$
Just a note for people who may wonder at how the solution was arrived at. When you read the corresponding material at codility.com/media/train/1-TimeComplexity.pdf, accessed via app.codility.com/programmers/lessons/3-time_complexity, it explains the optimal solution for finding the sum of integers 1..N. This solution can be applied to this problem, since we can find the sum of integers 1..N+1, and then subtract the sum of the integers in the array, in order to find the missing integer in the array.
$endgroup$
– James Ray
46 mins ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
With your JavaScript version, there is not much to optimize. So I am just going to provide some minor improvements:
- Within a function, it is better to declare your variables using the
varkeyword. You should apply this to theiinsidefor()loop - The JavaScript interpreter is a single thread: this means, unfortunately, you can not perform real parallelism to sum different chunks of the array.
- You can choose better variables and function names.
answered Jun 8 '17 at 15:36
Billal BegueradjBillal Begueradj
1
$endgroup$
add a comment |
$begingroup$
A minor modification:
function solution(A) {
const size = A.length;
let sum = 0;
for (let int of A){
sum += int;
}
return (((size + 1)*(size + 2))/2) - sum
}
Note that I've kept the function name because it is what the exercises/tests in Codility use.
As noted in the lesson material, the input N is an integer within the range [0..100,000]; so $O(n)$ or $O(Nlog{N})$ are acceptable time complexities.
The dominant operation in this function is sum += int; (repeated in the loop N times). Other than that, we have a constant number of other operations, not e.g. a nested loop where the input or another variable of the same order is halved in each iteration of the loop, which would be $O(Nlog{N})$ time complexity. So both of our solutions are $O(n)$ complexity.
answered 21 mins ago
James RayJames Ray
1012
New contributor
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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%2f165195%2fcodility-permmissingelem-solution%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
With your JavaScript version, there is not much to optimize. So I am just going to provide some minor improvements:
- Within a function, it is better to declare your variables using the
varkeyword. You should apply this to theiinsidefor()loop - The JavaScript interpreter is a single thread: this means, unfortunately, you can not perform real parallelism to sum different chunks of the array.
- You can choose better variables and function names.
answered Jun 8 '17 at 15:36
Billal BegueradjBillal Begueradj
1
$endgroup$
add a comment |
$begingroup$
With your JavaScript version, there is not much to optimize. So I am just going to provide some minor improvements:
- Within a function, it is better to declare your variables using the
varkeyword. You should apply this to theiinsidefor()loop - The JavaScript interpreter is a single thread: this means, unfortunately, you can not perform real parallelism to sum different chunks of the array.
- You can choose better variables and function names.
answered Jun 8 '17 at 15:36
Billal BegueradjBillal Begueradj
1
$endgroup$
add a comment |
$begingroup$
With your JavaScript version, there is not much to optimize. So I am just going to provide some minor improvements:
- Within a function, it is better to declare your variables using the
varkeyword. You should apply this to theiinsidefor()loop - The JavaScript interpreter is a single thread: this means, unfortunately, you can not perform real parallelism to sum different chunks of the array.
- You can choose better variables and function names.
answered Jun 8 '17 at 15:36
Billal BegueradjBillal Begueradj
1
$endgroup$
With your JavaScript version, there is not much to optimize. So I am just going to provide some minor improvements:
- Within a function, it is better to declare your variables using the
varkeyword. You should apply this to theiinsidefor()loop - The JavaScript interpreter is a single thread: this means, unfortunately, you can not perform real parallelism to sum different chunks of the array.
- You can choose better variables and function names.
answered Jun 8 '17 at 15:36
Billal BegueradjBillal Begueradj
1
answered Jun 8 '17 at 15:36
Billal BegueradjBillal Begueradj
1
answered Jun 8 '17 at 15:36
Billal BegueradjBillal Begueradj
1
answered Jun 8 '17 at 15:36
Billal BegueradjBillal Begueradj
1
1
add a comment |
add a comment |
$begingroup$
A minor modification:
function solution(A) {
const size = A.length;
let sum = 0;
for (let int of A){
sum += int;
}
return (((size + 1)*(size + 2))/2) - sum
}
Note that I've kept the function name because it is what the exercises/tests in Codility use.
As noted in the lesson material, the input N is an integer within the range [0..100,000]; so $O(n)$ or $O(Nlog{N})$ are acceptable time complexities.
The dominant operation in this function is sum += int; (repeated in the loop N times). Other than that, we have a constant number of other operations, not e.g. a nested loop where the input or another variable of the same order is halved in each iteration of the loop, which would be $O(Nlog{N})$ time complexity. So both of our solutions are $O(n)$ complexity.
answered 21 mins ago
James RayJames Ray
1012
New contributor
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
A minor modification:
function solution(A) {
const size = A.length;
let sum = 0;
for (let int of A){
sum += int;
}
return (((size + 1)*(size + 2))/2) - sum
}
Note that I've kept the function name because it is what the exercises/tests in Codility use.
As noted in the lesson material, the input N is an integer within the range [0..100,000]; so $O(n)$ or $O(Nlog{N})$ are acceptable time complexities.
The dominant operation in this function is sum += int; (repeated in the loop N times). Other than that, we have a constant number of other operations, not e.g. a nested loop where the input or another variable of the same order is halved in each iteration of the loop, which would be $O(Nlog{N})$ time complexity. So both of our solutions are $O(n)$ complexity.
answered 21 mins ago
James RayJames Ray
1012
New contributor
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
A minor modification:
function solution(A) {
const size = A.length;
let sum = 0;
for (let int of A){
sum += int;
}
return (((size + 1)*(size + 2))/2) - sum
}
Note that I've kept the function name because it is what the exercises/tests in Codility use.
As noted in the lesson material, the input N is an integer within the range [0..100,000]; so $O(n)$ or $O(Nlog{N})$ are acceptable time complexities.
The dominant operation in this function is sum += int; (repeated in the loop N times). Other than that, we have a constant number of other operations, not e.g. a nested loop where the input or another variable of the same order is halved in each iteration of the loop, which would be $O(Nlog{N})$ time complexity. So both of our solutions are $O(n)$ complexity.
answered 21 mins ago
James RayJames Ray
1012
New contributor
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
A minor modification:
function solution(A) {
const size = A.length;
let sum = 0;
for (let int of A){
sum += int;
}
return (((size + 1)*(size + 2))/2) - sum
}
Note that I've kept the function name because it is what the exercises/tests in Codility use.
As noted in the lesson material, the input N is an integer within the range [0..100,000]; so $O(n)$ or $O(Nlog{N})$ are acceptable time complexities.
The dominant operation in this function is sum += int; (repeated in the loop N times). Other than that, we have a constant number of other operations, not e.g. a nested loop where the input or another variable of the same order is halved in each iteration of the loop, which would be $O(Nlog{N})$ time complexity. So both of our solutions are $O(n)$ complexity.
answered 21 mins ago
James RayJames Ray
1012
New contributor
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 21 mins ago
James RayJames Ray
1012
New contributor
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 21 mins ago
James RayJames Ray
1012
answered 21 mins ago
James RayJames Ray
1012
1012
New contributor
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
James Ray is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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%2f165195%2fcodility-permmissingelem-solution%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
1
$begingroup$
Have you looked at this related question?
$endgroup$
– yuri
Jun 7 '17 at 20:26
$begingroup$
Can you share a performance test which reveals $O(Nlog{N})$ complexity?
$endgroup$
– vnp
Jun 8 '17 at 1:52
$begingroup$
Just a note for people who may wonder at how the solution was arrived at. When you read the corresponding material at codility.com/media/train/1-TimeComplexity.pdf, accessed via app.codility.com/programmers/lessons/3-time_complexity, it explains the optimal solution for finding the sum of integers 1..N. This solution can be applied to this problem, since we can find the sum of integers 1..N+1, and then subtract the sum of the integers in the array, in order to find the missing integer in the array.
$endgroup$
– James Ray
46 mins ago