Find value that occurs in odd number of elements
$begingroup$
I am trying to solve the following exercise using Javascript:
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
I have written the following code.
function solution(A) {
var pop;
if(!A.length)
return 0;
while(A.length){
pop = A.shift();
let pos = A.indexOf(pop);
if(pos >-1){
A.splice(pos,1);
} else {
return pop
}
}
return pop;
}
The correctness seems to be fine but it fails the performance test. The order shown is O(N**2).
- Any explanation why it shows exponential timing (I have not used any
nested loops)? - Any suggestions on what would be the optimized code which will run on O(N) having space complexity O(1)?
javascript algorithm array time-limit-exceeded iteration
$endgroup$
add a comment |
$begingroup$
I am trying to solve the following exercise using Javascript:
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
I have written the following code.
function solution(A) {
var pop;
if(!A.length)
return 0;
while(A.length){
pop = A.shift();
let pos = A.indexOf(pop);
if(pos >-1){
A.splice(pos,1);
} else {
return pop
}
}
return pop;
}
The correctness seems to be fine but it fails the performance test. The order shown is O(N**2).
- Any explanation why it shows exponential timing (I have not used any
nested loops)? - Any suggestions on what would be the optimized code which will run on O(N) having space complexity O(1)?
javascript algorithm array time-limit-exceeded iteration
$endgroup$
add a comment |
$begingroup$
I am trying to solve the following exercise using Javascript:
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
I have written the following code.
function solution(A) {
var pop;
if(!A.length)
return 0;
while(A.length){
pop = A.shift();
let pos = A.indexOf(pop);
if(pos >-1){
A.splice(pos,1);
} else {
return pop
}
}
return pop;
}
The correctness seems to be fine but it fails the performance test. The order shown is O(N**2).
- Any explanation why it shows exponential timing (I have not used any
nested loops)? - Any suggestions on what would be the optimized code which will run on O(N) having space complexity O(1)?
javascript algorithm array time-limit-exceeded iteration
$endgroup$
I am trying to solve the following exercise using Javascript:
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
I have written the following code.
function solution(A) {
var pop;
if(!A.length)
return 0;
while(A.length){
pop = A.shift();
let pos = A.indexOf(pop);
if(pos >-1){
A.splice(pos,1);
} else {
return pop
}
}
return pop;
}
The correctness seems to be fine but it fails the performance test. The order shown is O(N**2).
- Any explanation why it shows exponential timing (I have not used any
nested loops)? - Any suggestions on what would be the optimized code which will run on O(N) having space complexity O(1)?
javascript algorithm array time-limit-exceeded iteration
javascript algorithm array time-limit-exceeded iteration
edited Jul 12 '18 at 22:59
Dannnno
5,5071849
5,5071849
asked Jul 12 '18 at 21:12
Anirban BeraAnirban Bera
83
83
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Any explanation why it shows exponential timing (I have not used any nested loops)?
Inside the while loop you have A.indexOf(pop);
which is the second inner loop. It iterates over each item until it finds the match. You can use a Set which uses a hash table to locate items.
Any suggestions on what would be the optimized code which will run on O(N)?
Use a Set
. For each item first check the set, if its there remove it and the item, else add the item to the set and move to the next item. When done you should have one item remaining in the set, that will be the odd one out.
function findOdd(arr){
const found = new Set();
while (arr.length > 0) {
const val = arr.pop(); // or use shift
// if val in found remove it from the set
if (found.has(val)) { found.delete(val) }
else { found.add(val) } // else add it to the set
}
return [...found.values()][0];
}
$endgroup$
$begingroup$
Elegant solution! Can you confirm the worst case space complexity of this? I think it is O(1) (not counting the storage required for input arguments) - correct me if I'm wrong.
$endgroup$
– Anirban Bera
Jul 13 '18 at 4:26
$begingroup$
@AnirbanBera Sorry O(n) space for hash tables. See wiki en.wikipedia.org/wiki/Hash_table
$endgroup$
– Blindman67
Jul 13 '18 at 5:01
$begingroup$
// if val in found remove it from the set
comment is useless.
$endgroup$
– Stexxe
Jul 13 '18 at 11:37
add a comment |
$begingroup$
The solution with an O(N) time complexity with O(1) space is a little bit hacky. The solution is to xor each number together. some important properties of xor are:
- xor of two identical numbers is zero.
- xor of any number and zero is the number.
- xor is commutative.
- xor is associative.
example:
A = [9, 3, 9, 3, 9, 7, 9]
the solution to this example is:
(((((9^3)^9)^3)^9)^7)^9
= 9^3^9^3^9^7^9 (4)
= 9^9^9^9^3^3^7 (3)
= (9^9)^(9^9)^(3^3)^7 (3)
= 0^0^0^7 (1)
= 7 (2)
$endgroup$
add a comment |
$begingroup$
We can find unpaired number by sorting array of integers and searching for one, which has no adjacent with same value.
My suggested solution:
const nextIsDifferent = (el, index, arr) => ((index + 1) % 2 === 1 && el !== arr[index + 1]);
const findUnpaired = (arr) => arr.sort().find(nextIsDifferent);
console.log(findUnpaired([9, 3, 9, 3, 9, 7, 9]));
$endgroup$
$begingroup$
You have supplied an alternative solution, without saying how or why it is better. If you could add some details, this would make a nice answer.
$endgroup$
– Graipher
Jul 13 '18 at 12:33
$begingroup$
This is also a nice solution. Can you please elaborate on the time complexity of it? will it be O(N) or O(NlogN) <for sorting>?
$endgroup$
– Anirban Bera
Jul 13 '18 at 15:58
$begingroup$
I think it's O(NlogN)
$endgroup$
– Stexxe
Jul 13 '18 at 20:41
$begingroup$
I did this in Codility lesson, albeit I was using C#. At first, I used LINQ but the performance was bad,I changed to this algo and got 100% score.
$endgroup$
– Rosdi Kasim
Feb 5 at 14:16
add a comment |
$begingroup$
Initially I came up with this solution:
function solution(A) {
let arr = ;
for (let int of A) {
if (arr[int] === false) {
arr[int] = true
} else (
// only one element found so far
arr[int] = false
)
}
return arr.indexOf(false);
}
However, it is either O(n) or O(nlog(n)) on Codility, and fails the last performance test.
@Peter's approach seems like the best.
I cheated and modified from this Java solution:
class Solution {
public int solution(int A) {
int result = 0;
for (int x : A) result ^= x;
return result;
}
}
to get this solution, which has a 100% score on Codility (try it yourself):
function solution(A) {
var result = 0;
for (let int of A) {
result ^= int;
}
return result;
}
New contributor
$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%2f198388%2ffind-value-that-occurs-in-odd-number-of-elements%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Any explanation why it shows exponential timing (I have not used any nested loops)?
Inside the while loop you have A.indexOf(pop);
which is the second inner loop. It iterates over each item until it finds the match. You can use a Set which uses a hash table to locate items.
Any suggestions on what would be the optimized code which will run on O(N)?
Use a Set
. For each item first check the set, if its there remove it and the item, else add the item to the set and move to the next item. When done you should have one item remaining in the set, that will be the odd one out.
function findOdd(arr){
const found = new Set();
while (arr.length > 0) {
const val = arr.pop(); // or use shift
// if val in found remove it from the set
if (found.has(val)) { found.delete(val) }
else { found.add(val) } // else add it to the set
}
return [...found.values()][0];
}
$endgroup$
$begingroup$
Elegant solution! Can you confirm the worst case space complexity of this? I think it is O(1) (not counting the storage required for input arguments) - correct me if I'm wrong.
$endgroup$
– Anirban Bera
Jul 13 '18 at 4:26
$begingroup$
@AnirbanBera Sorry O(n) space for hash tables. See wiki en.wikipedia.org/wiki/Hash_table
$endgroup$
– Blindman67
Jul 13 '18 at 5:01
$begingroup$
// if val in found remove it from the set
comment is useless.
$endgroup$
– Stexxe
Jul 13 '18 at 11:37
add a comment |
$begingroup$
Any explanation why it shows exponential timing (I have not used any nested loops)?
Inside the while loop you have A.indexOf(pop);
which is the second inner loop. It iterates over each item until it finds the match. You can use a Set which uses a hash table to locate items.
Any suggestions on what would be the optimized code which will run on O(N)?
Use a Set
. For each item first check the set, if its there remove it and the item, else add the item to the set and move to the next item. When done you should have one item remaining in the set, that will be the odd one out.
function findOdd(arr){
const found = new Set();
while (arr.length > 0) {
const val = arr.pop(); // or use shift
// if val in found remove it from the set
if (found.has(val)) { found.delete(val) }
else { found.add(val) } // else add it to the set
}
return [...found.values()][0];
}
$endgroup$
$begingroup$
Elegant solution! Can you confirm the worst case space complexity of this? I think it is O(1) (not counting the storage required for input arguments) - correct me if I'm wrong.
$endgroup$
– Anirban Bera
Jul 13 '18 at 4:26
$begingroup$
@AnirbanBera Sorry O(n) space for hash tables. See wiki en.wikipedia.org/wiki/Hash_table
$endgroup$
– Blindman67
Jul 13 '18 at 5:01
$begingroup$
// if val in found remove it from the set
comment is useless.
$endgroup$
– Stexxe
Jul 13 '18 at 11:37
add a comment |
$begingroup$
Any explanation why it shows exponential timing (I have not used any nested loops)?
Inside the while loop you have A.indexOf(pop);
which is the second inner loop. It iterates over each item until it finds the match. You can use a Set which uses a hash table to locate items.
Any suggestions on what would be the optimized code which will run on O(N)?
Use a Set
. For each item first check the set, if its there remove it and the item, else add the item to the set and move to the next item. When done you should have one item remaining in the set, that will be the odd one out.
function findOdd(arr){
const found = new Set();
while (arr.length > 0) {
const val = arr.pop(); // or use shift
// if val in found remove it from the set
if (found.has(val)) { found.delete(val) }
else { found.add(val) } // else add it to the set
}
return [...found.values()][0];
}
$endgroup$
Any explanation why it shows exponential timing (I have not used any nested loops)?
Inside the while loop you have A.indexOf(pop);
which is the second inner loop. It iterates over each item until it finds the match. You can use a Set which uses a hash table to locate items.
Any suggestions on what would be the optimized code which will run on O(N)?
Use a Set
. For each item first check the set, if its there remove it and the item, else add the item to the set and move to the next item. When done you should have one item remaining in the set, that will be the odd one out.
function findOdd(arr){
const found = new Set();
while (arr.length > 0) {
const val = arr.pop(); // or use shift
// if val in found remove it from the set
if (found.has(val)) { found.delete(val) }
else { found.add(val) } // else add it to the set
}
return [...found.values()][0];
}
edited Jul 13 '18 at 4:03
answered Jul 12 '18 at 21:32
Blindman67Blindman67
8,1351521
8,1351521
$begingroup$
Elegant solution! Can you confirm the worst case space complexity of this? I think it is O(1) (not counting the storage required for input arguments) - correct me if I'm wrong.
$endgroup$
– Anirban Bera
Jul 13 '18 at 4:26
$begingroup$
@AnirbanBera Sorry O(n) space for hash tables. See wiki en.wikipedia.org/wiki/Hash_table
$endgroup$
– Blindman67
Jul 13 '18 at 5:01
$begingroup$
// if val in found remove it from the set
comment is useless.
$endgroup$
– Stexxe
Jul 13 '18 at 11:37
add a comment |
$begingroup$
Elegant solution! Can you confirm the worst case space complexity of this? I think it is O(1) (not counting the storage required for input arguments) - correct me if I'm wrong.
$endgroup$
– Anirban Bera
Jul 13 '18 at 4:26
$begingroup$
@AnirbanBera Sorry O(n) space for hash tables. See wiki en.wikipedia.org/wiki/Hash_table
$endgroup$
– Blindman67
Jul 13 '18 at 5:01
$begingroup$
// if val in found remove it from the set
comment is useless.
$endgroup$
– Stexxe
Jul 13 '18 at 11:37
$begingroup$
Elegant solution! Can you confirm the worst case space complexity of this? I think it is O(1) (not counting the storage required for input arguments) - correct me if I'm wrong.
$endgroup$
– Anirban Bera
Jul 13 '18 at 4:26
$begingroup$
Elegant solution! Can you confirm the worst case space complexity of this? I think it is O(1) (not counting the storage required for input arguments) - correct me if I'm wrong.
$endgroup$
– Anirban Bera
Jul 13 '18 at 4:26
$begingroup$
@AnirbanBera Sorry O(n) space for hash tables. See wiki en.wikipedia.org/wiki/Hash_table
$endgroup$
– Blindman67
Jul 13 '18 at 5:01
$begingroup$
@AnirbanBera Sorry O(n) space for hash tables. See wiki en.wikipedia.org/wiki/Hash_table
$endgroup$
– Blindman67
Jul 13 '18 at 5:01
$begingroup$
// if val in found remove it from the set
comment is useless.$endgroup$
– Stexxe
Jul 13 '18 at 11:37
$begingroup$
// if val in found remove it from the set
comment is useless.$endgroup$
– Stexxe
Jul 13 '18 at 11:37
add a comment |
$begingroup$
The solution with an O(N) time complexity with O(1) space is a little bit hacky. The solution is to xor each number together. some important properties of xor are:
- xor of two identical numbers is zero.
- xor of any number and zero is the number.
- xor is commutative.
- xor is associative.
example:
A = [9, 3, 9, 3, 9, 7, 9]
the solution to this example is:
(((((9^3)^9)^3)^9)^7)^9
= 9^3^9^3^9^7^9 (4)
= 9^9^9^9^3^3^7 (3)
= (9^9)^(9^9)^(3^3)^7 (3)
= 0^0^0^7 (1)
= 7 (2)
$endgroup$
add a comment |
$begingroup$
The solution with an O(N) time complexity with O(1) space is a little bit hacky. The solution is to xor each number together. some important properties of xor are:
- xor of two identical numbers is zero.
- xor of any number and zero is the number.
- xor is commutative.
- xor is associative.
example:
A = [9, 3, 9, 3, 9, 7, 9]
the solution to this example is:
(((((9^3)^9)^3)^9)^7)^9
= 9^3^9^3^9^7^9 (4)
= 9^9^9^9^3^3^7 (3)
= (9^9)^(9^9)^(3^3)^7 (3)
= 0^0^0^7 (1)
= 7 (2)
$endgroup$
add a comment |
$begingroup$
The solution with an O(N) time complexity with O(1) space is a little bit hacky. The solution is to xor each number together. some important properties of xor are:
- xor of two identical numbers is zero.
- xor of any number and zero is the number.
- xor is commutative.
- xor is associative.
example:
A = [9, 3, 9, 3, 9, 7, 9]
the solution to this example is:
(((((9^3)^9)^3)^9)^7)^9
= 9^3^9^3^9^7^9 (4)
= 9^9^9^9^3^3^7 (3)
= (9^9)^(9^9)^(3^3)^7 (3)
= 0^0^0^7 (1)
= 7 (2)
$endgroup$
The solution with an O(N) time complexity with O(1) space is a little bit hacky. The solution is to xor each number together. some important properties of xor are:
- xor of two identical numbers is zero.
- xor of any number and zero is the number.
- xor is commutative.
- xor is associative.
example:
A = [9, 3, 9, 3, 9, 7, 9]
the solution to this example is:
(((((9^3)^9)^3)^9)^7)^9
= 9^3^9^3^9^7^9 (4)
= 9^9^9^9^3^3^7 (3)
= (9^9)^(9^9)^(3^3)^7 (3)
= 0^0^0^7 (1)
= 7 (2)
edited Jul 13 '18 at 3:52
answered Jul 12 '18 at 21:49
PeterPeter
708112
708112
add a comment |
add a comment |
$begingroup$
We can find unpaired number by sorting array of integers and searching for one, which has no adjacent with same value.
My suggested solution:
const nextIsDifferent = (el, index, arr) => ((index + 1) % 2 === 1 && el !== arr[index + 1]);
const findUnpaired = (arr) => arr.sort().find(nextIsDifferent);
console.log(findUnpaired([9, 3, 9, 3, 9, 7, 9]));
$endgroup$
$begingroup$
You have supplied an alternative solution, without saying how or why it is better. If you could add some details, this would make a nice answer.
$endgroup$
– Graipher
Jul 13 '18 at 12:33
$begingroup$
This is also a nice solution. Can you please elaborate on the time complexity of it? will it be O(N) or O(NlogN) <for sorting>?
$endgroup$
– Anirban Bera
Jul 13 '18 at 15:58
$begingroup$
I think it's O(NlogN)
$endgroup$
– Stexxe
Jul 13 '18 at 20:41
$begingroup$
I did this in Codility lesson, albeit I was using C#. At first, I used LINQ but the performance was bad,I changed to this algo and got 100% score.
$endgroup$
– Rosdi Kasim
Feb 5 at 14:16
add a comment |
$begingroup$
We can find unpaired number by sorting array of integers and searching for one, which has no adjacent with same value.
My suggested solution:
const nextIsDifferent = (el, index, arr) => ((index + 1) % 2 === 1 && el !== arr[index + 1]);
const findUnpaired = (arr) => arr.sort().find(nextIsDifferent);
console.log(findUnpaired([9, 3, 9, 3, 9, 7, 9]));
$endgroup$
$begingroup$
You have supplied an alternative solution, without saying how or why it is better. If you could add some details, this would make a nice answer.
$endgroup$
– Graipher
Jul 13 '18 at 12:33
$begingroup$
This is also a nice solution. Can you please elaborate on the time complexity of it? will it be O(N) or O(NlogN) <for sorting>?
$endgroup$
– Anirban Bera
Jul 13 '18 at 15:58
$begingroup$
I think it's O(NlogN)
$endgroup$
– Stexxe
Jul 13 '18 at 20:41
$begingroup$
I did this in Codility lesson, albeit I was using C#. At first, I used LINQ but the performance was bad,I changed to this algo and got 100% score.
$endgroup$
– Rosdi Kasim
Feb 5 at 14:16
add a comment |
$begingroup$
We can find unpaired number by sorting array of integers and searching for one, which has no adjacent with same value.
My suggested solution:
const nextIsDifferent = (el, index, arr) => ((index + 1) % 2 === 1 && el !== arr[index + 1]);
const findUnpaired = (arr) => arr.sort().find(nextIsDifferent);
console.log(findUnpaired([9, 3, 9, 3, 9, 7, 9]));
$endgroup$
We can find unpaired number by sorting array of integers and searching for one, which has no adjacent with same value.
My suggested solution:
const nextIsDifferent = (el, index, arr) => ((index + 1) % 2 === 1 && el !== arr[index + 1]);
const findUnpaired = (arr) => arr.sort().find(nextIsDifferent);
console.log(findUnpaired([9, 3, 9, 3, 9, 7, 9]));
edited Jul 13 '18 at 12:49
answered Jul 13 '18 at 12:08
StexxeStexxe
4468
4468
$begingroup$
You have supplied an alternative solution, without saying how or why it is better. If you could add some details, this would make a nice answer.
$endgroup$
– Graipher
Jul 13 '18 at 12:33
$begingroup$
This is also a nice solution. Can you please elaborate on the time complexity of it? will it be O(N) or O(NlogN) <for sorting>?
$endgroup$
– Anirban Bera
Jul 13 '18 at 15:58
$begingroup$
I think it's O(NlogN)
$endgroup$
– Stexxe
Jul 13 '18 at 20:41
$begingroup$
I did this in Codility lesson, albeit I was using C#. At first, I used LINQ but the performance was bad,I changed to this algo and got 100% score.
$endgroup$
– Rosdi Kasim
Feb 5 at 14:16
add a comment |
$begingroup$
You have supplied an alternative solution, without saying how or why it is better. If you could add some details, this would make a nice answer.
$endgroup$
– Graipher
Jul 13 '18 at 12:33
$begingroup$
This is also a nice solution. Can you please elaborate on the time complexity of it? will it be O(N) or O(NlogN) <for sorting>?
$endgroup$
– Anirban Bera
Jul 13 '18 at 15:58
$begingroup$
I think it's O(NlogN)
$endgroup$
– Stexxe
Jul 13 '18 at 20:41
$begingroup$
I did this in Codility lesson, albeit I was using C#. At first, I used LINQ but the performance was bad,I changed to this algo and got 100% score.
$endgroup$
– Rosdi Kasim
Feb 5 at 14:16
$begingroup$
You have supplied an alternative solution, without saying how or why it is better. If you could add some details, this would make a nice answer.
$endgroup$
– Graipher
Jul 13 '18 at 12:33
$begingroup$
You have supplied an alternative solution, without saying how or why it is better. If you could add some details, this would make a nice answer.
$endgroup$
– Graipher
Jul 13 '18 at 12:33
$begingroup$
This is also a nice solution. Can you please elaborate on the time complexity of it? will it be O(N) or O(NlogN) <for sorting>?
$endgroup$
– Anirban Bera
Jul 13 '18 at 15:58
$begingroup$
This is also a nice solution. Can you please elaborate on the time complexity of it? will it be O(N) or O(NlogN) <for sorting>?
$endgroup$
– Anirban Bera
Jul 13 '18 at 15:58
$begingroup$
I think it's O(NlogN)
$endgroup$
– Stexxe
Jul 13 '18 at 20:41
$begingroup$
I think it's O(NlogN)
$endgroup$
– Stexxe
Jul 13 '18 at 20:41
$begingroup$
I did this in Codility lesson, albeit I was using C#. At first, I used LINQ but the performance was bad,I changed to this algo and got 100% score.
$endgroup$
– Rosdi Kasim
Feb 5 at 14:16
$begingroup$
I did this in Codility lesson, albeit I was using C#. At first, I used LINQ but the performance was bad,I changed to this algo and got 100% score.
$endgroup$
– Rosdi Kasim
Feb 5 at 14:16
add a comment |
$begingroup$
Initially I came up with this solution:
function solution(A) {
let arr = ;
for (let int of A) {
if (arr[int] === false) {
arr[int] = true
} else (
// only one element found so far
arr[int] = false
)
}
return arr.indexOf(false);
}
However, it is either O(n) or O(nlog(n)) on Codility, and fails the last performance test.
@Peter's approach seems like the best.
I cheated and modified from this Java solution:
class Solution {
public int solution(int A) {
int result = 0;
for (int x : A) result ^= x;
return result;
}
}
to get this solution, which has a 100% score on Codility (try it yourself):
function solution(A) {
var result = 0;
for (let int of A) {
result ^= int;
}
return result;
}
New contributor
$endgroup$
add a comment |
$begingroup$
Initially I came up with this solution:
function solution(A) {
let arr = ;
for (let int of A) {
if (arr[int] === false) {
arr[int] = true
} else (
// only one element found so far
arr[int] = false
)
}
return arr.indexOf(false);
}
However, it is either O(n) or O(nlog(n)) on Codility, and fails the last performance test.
@Peter's approach seems like the best.
I cheated and modified from this Java solution:
class Solution {
public int solution(int A) {
int result = 0;
for (int x : A) result ^= x;
return result;
}
}
to get this solution, which has a 100% score on Codility (try it yourself):
function solution(A) {
var result = 0;
for (let int of A) {
result ^= int;
}
return result;
}
New contributor
$endgroup$
add a comment |
$begingroup$
Initially I came up with this solution:
function solution(A) {
let arr = ;
for (let int of A) {
if (arr[int] === false) {
arr[int] = true
} else (
// only one element found so far
arr[int] = false
)
}
return arr.indexOf(false);
}
However, it is either O(n) or O(nlog(n)) on Codility, and fails the last performance test.
@Peter's approach seems like the best.
I cheated and modified from this Java solution:
class Solution {
public int solution(int A) {
int result = 0;
for (int x : A) result ^= x;
return result;
}
}
to get this solution, which has a 100% score on Codility (try it yourself):
function solution(A) {
var result = 0;
for (let int of A) {
result ^= int;
}
return result;
}
New contributor
$endgroup$
Initially I came up with this solution:
function solution(A) {
let arr = ;
for (let int of A) {
if (arr[int] === false) {
arr[int] = true
} else (
// only one element found so far
arr[int] = false
)
}
return arr.indexOf(false);
}
However, it is either O(n) or O(nlog(n)) on Codility, and fails the last performance test.
@Peter's approach seems like the best.
I cheated and modified from this Java solution:
class Solution {
public int solution(int A) {
int result = 0;
for (int x : A) result ^= x;
return result;
}
}
to get this solution, which has a 100% score on Codility (try it yourself):
function solution(A) {
var result = 0;
for (let int of A) {
result ^= int;
}
return result;
}
New contributor
New contributor
answered 41 mins ago
James RayJames Ray
1012
1012
New contributor
New contributor
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%2f198388%2ffind-value-that-occurs-in-odd-number-of-elements%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