Finding Repeat and missing numbers in an array
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
0
down vote
favorite
Problem Statement:
You are given a read-only array of n integers from 1 to n. Each
integer appears exactly once except A which appears twice and B which
is missing.
Return A and B.
Example
Input:[3 1 2 5 3]
Output:[3, 4]
A = 3, B = 4
I wrote the following code:
def repeated_number(number_array):
pair_A_B =
n = len(number_array)
for i in number_array:
if(number_array.count(i)==2):
pair_A_B.append(i)
break
sample = range(1,n+1)
diff = list(set(sample)-set(number_array))
pair_A_B.append(diff[0])
return pair_A_B
sample_input = [3,1,2,3,5]
print(repeated_number(sample_input))
The code works fine for this problem on my laptop but when I try to submit it on a coding forum it says my code is not efficient. How can I make it efficient in terms of time?
python algorithm array set
edited Jun 24 at 16:09
Jamal♦
30.1k11114225
asked Jun 24 at 14:48
Prathu Baronia
1
add a comment |Â
up vote
0
down vote
favorite
Problem Statement:
You are given a read-only array of n integers from 1 to n. Each
integer appears exactly once except A which appears twice and B which
is missing.
Return A and B.
Example
Input:[3 1 2 5 3]
Output:[3, 4]
A = 3, B = 4
I wrote the following code:
def repeated_number(number_array):
pair_A_B =
n = len(number_array)
for i in number_array:
if(number_array.count(i)==2):
pair_A_B.append(i)
break
sample = range(1,n+1)
diff = list(set(sample)-set(number_array))
pair_A_B.append(diff[0])
return pair_A_B
sample_input = [3,1,2,3,5]
print(repeated_number(sample_input))
The code works fine for this problem on my laptop but when I try to submit it on a coding forum it says my code is not efficient. How can I make it efficient in terms of time?
python algorithm array set
edited Jun 24 at 16:09
Jamal♦
30.1k11114225
asked Jun 24 at 14:48
Prathu Baronia
1
I don't have time to write a full answer, but it comes down to this: you have a turned an O(n) problem into an O(n^2) problem. Here is the algorithm I would use: create a list of bools that is the size ofnumber_array. Initialize the elements to false with a list comprehension. Now, iterate throughnumber_array. For each number found, check the value in the bool list at that index - 1. If it's true, add that number to the output list. If it's false, set it to true. Then iterate through the list of bools. Once you find an element that is false, add the index of that element + 1 to the...
– Mike Borkland
Jun 24 at 15:51
output list. Break from the loop and return the output list.
– Mike Borkland
Jun 24 at 15:51
1
Did you do some research? Various more efficient methods are demonstrated for example at geeksforgeeks.org/find-a-repeating-and-a-missing-number and stackoverflow.com/questions/5766936/…. – And here is another CR question about the same problem codereview.stackexchange.com/questions/194379/…
– Martin R
Jun 24 at 16:05
1
@MartinR my bad, I should have checked.
– Prathu Baronia
Jun 24 at 16:16
I actually solved by having an empty hashmap and started populating it as I proceeded and had a check on whenever the value goes to 2
– Prathu Baronia
Jun 28 at 11:45
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Problem Statement:
You are given a read-only array of n integers from 1 to n. Each
integer appears exactly once except A which appears twice and B which
is missing.
Return A and B.
Example
Input:[3 1 2 5 3]
Output:[3, 4]
A = 3, B = 4
I wrote the following code:
def repeated_number(number_array):
pair_A_B =
n = len(number_array)
for i in number_array:
if(number_array.count(i)==2):
pair_A_B.append(i)
break
sample = range(1,n+1)
diff = list(set(sample)-set(number_array))
pair_A_B.append(diff[0])
return pair_A_B
sample_input = [3,1,2,3,5]
print(repeated_number(sample_input))
The code works fine for this problem on my laptop but when I try to submit it on a coding forum it says my code is not efficient. How can I make it efficient in terms of time?
python algorithm array set
edited Jun 24 at 16:09
Jamal♦
30.1k11114225
asked Jun 24 at 14:48
Prathu Baronia
1
Problem Statement:
You are given a read-only array of n integers from 1 to n. Each
integer appears exactly once except A which appears twice and B which
is missing.
Return A and B.
Example
Input:[3 1 2 5 3]
Output:[3, 4]
A = 3, B = 4
I wrote the following code:
def repeated_number(number_array):
pair_A_B =
n = len(number_array)
for i in number_array:
if(number_array.count(i)==2):
pair_A_B.append(i)
break
sample = range(1,n+1)
diff = list(set(sample)-set(number_array))
pair_A_B.append(diff[0])
return pair_A_B
sample_input = [3,1,2,3,5]
print(repeated_number(sample_input))
The code works fine for this problem on my laptop but when I try to submit it on a coding forum it says my code is not efficient. How can I make it efficient in terms of time?
python algorithm array set
edited Jun 24 at 16:09
Jamal♦
30.1k11114225
asked Jun 24 at 14:48
Prathu Baronia
1
edited Jun 24 at 16:09
Jamal♦
30.1k11114225
edited Jun 24 at 16:09
Jamal♦
30.1k11114225
edited Jun 24 at 16:09
Jamal♦
30.1k11114225
30.1k11114225
asked Jun 24 at 14:48
Prathu Baronia
1
asked Jun 24 at 14:48
Prathu Baronia
1
asked Jun 24 at 14:48
Prathu Baronia
1
1
I don't have time to write a full answer, but it comes down to this: you have a turned an O(n) problem into an O(n^2) problem. Here is the algorithm I would use: create a list of bools that is the size ofnumber_array. Initialize the elements to false with a list comprehension. Now, iterate throughnumber_array. For each number found, check the value in the bool list at that index - 1. If it's true, add that number to the output list. If it's false, set it to true. Then iterate through the list of bools. Once you find an element that is false, add the index of that element + 1 to the...
– Mike Borkland
Jun 24 at 15:51
output list. Break from the loop and return the output list.
– Mike Borkland
Jun 24 at 15:51
1
Did you do some research? Various more efficient methods are demonstrated for example at geeksforgeeks.org/find-a-repeating-and-a-missing-number and stackoverflow.com/questions/5766936/…. – And here is another CR question about the same problem codereview.stackexchange.com/questions/194379/…
– Martin R
Jun 24 at 16:05
1
@MartinR my bad, I should have checked.
– Prathu Baronia
Jun 24 at 16:16
I actually solved by having an empty hashmap and started populating it as I proceeded and had a check on whenever the value goes to 2
– Prathu Baronia
Jun 28 at 11:45
add a comment |Â
I don't have time to write a full answer, but it comes down to this: you have a turned an O(n) problem into an O(n^2) problem. Here is the algorithm I would use: create a list of bools that is the size ofnumber_array. Initialize the elements to false with a list comprehension. Now, iterate throughnumber_array. For each number found, check the value in the bool list at that index - 1. If it's true, add that number to the output list. If it's false, set it to true. Then iterate through the list of bools. Once you find an element that is false, add the index of that element + 1 to the...
– Mike Borkland
Jun 24 at 15:51
output list. Break from the loop and return the output list.
– Mike Borkland
Jun 24 at 15:51
1
Did you do some research? Various more efficient methods are demonstrated for example at geeksforgeeks.org/find-a-repeating-and-a-missing-number and stackoverflow.com/questions/5766936/…. – And here is another CR question about the same problem codereview.stackexchange.com/questions/194379/…
– Martin R
Jun 24 at 16:05
1
@MartinR my bad, I should have checked.
– Prathu Baronia
Jun 24 at 16:16
I actually solved by having an empty hashmap and started populating it as I proceeded and had a check on whenever the value goes to 2
– Prathu Baronia
Jun 28 at 11:45
I don't have time to write a full answer, but it comes down to this: you have a turned an O(n) problem into an O(n^2) problem. Here is the algorithm I would use: create a list of bools that is the size of
number_array. Initialize the elements to false with a list comprehension. Now, iterate through number_array. For each number found, check the value in the bool list at that index - 1. If it's true, add that number to the output list. If it's false, set it to true. Then iterate through the list of bools. Once you find an element that is false, add the index of that element + 1 to the...– Mike Borkland
Jun 24 at 15:51
I don't have time to write a full answer, but it comes down to this: you have a turned an O(n) problem into an O(n^2) problem. Here is the algorithm I would use: create a list of bools that is the size of
number_array. Initialize the elements to false with a list comprehension. Now, iterate through number_array. For each number found, check the value in the bool list at that index - 1. If it's true, add that number to the output list. If it's false, set it to true. Then iterate through the list of bools. Once you find an element that is false, add the index of that element + 1 to the...– Mike Borkland
Jun 24 at 15:51
output list. Break from the loop and return the output list.
– Mike Borkland
Jun 24 at 15:51
output list. Break from the loop and return the output list.
– Mike Borkland
Jun 24 at 15:51
1
1
Did you do some research? Various more efficient methods are demonstrated for example at geeksforgeeks.org/find-a-repeating-and-a-missing-number and stackoverflow.com/questions/5766936/…. – And here is another CR question about the same problem codereview.stackexchange.com/questions/194379/…
– Martin R
Jun 24 at 16:05
Did you do some research? Various more efficient methods are demonstrated for example at geeksforgeeks.org/find-a-repeating-and-a-missing-number and stackoverflow.com/questions/5766936/…. – And here is another CR question about the same problem codereview.stackexchange.com/questions/194379/…
– Martin R
Jun 24 at 16:05
1
1
@MartinR my bad, I should have checked.
– Prathu Baronia
Jun 24 at 16:16
@MartinR my bad, I should have checked.
– Prathu Baronia
Jun 24 at 16:16
I actually solved by having an empty hashmap and started populating it as I proceeded and had a check on whenever the value goes to 2
– Prathu Baronia
Jun 28 at 11:45
I actually solved by having an empty hashmap and started populating it as I proceeded and had a check on whenever the value goes to 2
– Prathu Baronia
Jun 28 at 11:45
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
In addition to answers given here, you may use collections module for more pythonic code.
import collections
[k for k, v in collections.Counter([1,2,3,3,5]).items() if v > 1]
# [3]
This is O(n).
answered Jun 28 at 12:21
sardok
1113
add a comment |Â
up vote
1
down vote
The problem lies in these 2 lines of code:
for i in number_array:
if(number_array.count(i)==2):
Here for each number you are counting the number of occurrences in the array. Now, by doing that, You are reiterating over the numbers which are already counted. The call to number_array.count() searches the entire array, which means even for the last element, it will start from the first and calculate the count. This makes the time complexity $O(n^2)$. But, it can be done in $O(n)$ time.
Instead of using count, store the numbers in a hash table. And for each new number check, if it already exists in the hash table. If so, that's your duplicate number - A.
Also, while iterating through the loop, add each number to the other, and get their sum (omitting the double occurrence of A). And since you have a series from 1..n,
sum(1..n) = n * (n + 1) / 2
So, the missing number is:
sum(1..n) - actual sum
edited Jun 28 at 17:20
Sam Onela
5,72961543
answered Jun 28 at 9:51
Sayan Bose
1111
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
In addition to answers given here, you may use collections module for more pythonic code.
import collections
[k for k, v in collections.Counter([1,2,3,3,5]).items() if v > 1]
# [3]
This is O(n).
answered Jun 28 at 12:21
sardok
1113
add a comment |Â
up vote
1
down vote
In addition to answers given here, you may use collections module for more pythonic code.
import collections
[k for k, v in collections.Counter([1,2,3,3,5]).items() if v > 1]
# [3]
This is O(n).
answered Jun 28 at 12:21
sardok
1113
add a comment |Â
up vote
1
down vote
up vote
1
down vote
In addition to answers given here, you may use collections module for more pythonic code.
import collections
[k for k, v in collections.Counter([1,2,3,3,5]).items() if v > 1]
# [3]
This is O(n).
answered Jun 28 at 12:21
sardok
1113
In addition to answers given here, you may use collections module for more pythonic code.
import collections
[k for k, v in collections.Counter([1,2,3,3,5]).items() if v > 1]
# [3]
This is O(n).
answered Jun 28 at 12:21
sardok
1113
answered Jun 28 at 12:21
sardok
1113
answered Jun 28 at 12:21
sardok
1113
answered Jun 28 at 12:21
sardok
1113
1113
add a comment |Â
add a comment |Â
up vote
1
down vote
The problem lies in these 2 lines of code:
for i in number_array:
if(number_array.count(i)==2):
Here for each number you are counting the number of occurrences in the array. Now, by doing that, You are reiterating over the numbers which are already counted. The call to number_array.count() searches the entire array, which means even for the last element, it will start from the first and calculate the count. This makes the time complexity $O(n^2)$. But, it can be done in $O(n)$ time.
Instead of using count, store the numbers in a hash table. And for each new number check, if it already exists in the hash table. If so, that's your duplicate number - A.
Also, while iterating through the loop, add each number to the other, and get their sum (omitting the double occurrence of A). And since you have a series from 1..n,
sum(1..n) = n * (n + 1) / 2
So, the missing number is:
sum(1..n) - actual sum
edited Jun 28 at 17:20
Sam Onela
5,72961543
answered Jun 28 at 9:51
Sayan Bose
1111
add a comment |Â
up vote
1
down vote
The problem lies in these 2 lines of code:
for i in number_array:
if(number_array.count(i)==2):
Here for each number you are counting the number of occurrences in the array. Now, by doing that, You are reiterating over the numbers which are already counted. The call to number_array.count() searches the entire array, which means even for the last element, it will start from the first and calculate the count. This makes the time complexity $O(n^2)$. But, it can be done in $O(n)$ time.
Instead of using count, store the numbers in a hash table. And for each new number check, if it already exists in the hash table. If so, that's your duplicate number - A.
Also, while iterating through the loop, add each number to the other, and get their sum (omitting the double occurrence of A). And since you have a series from 1..n,
sum(1..n) = n * (n + 1) / 2
So, the missing number is:
sum(1..n) - actual sum
edited Jun 28 at 17:20
Sam Onela
5,72961543
answered Jun 28 at 9:51
Sayan Bose
1111
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The problem lies in these 2 lines of code:
for i in number_array:
if(number_array.count(i)==2):
Here for each number you are counting the number of occurrences in the array. Now, by doing that, You are reiterating over the numbers which are already counted. The call to number_array.count() searches the entire array, which means even for the last element, it will start from the first and calculate the count. This makes the time complexity $O(n^2)$. But, it can be done in $O(n)$ time.
Instead of using count, store the numbers in a hash table. And for each new number check, if it already exists in the hash table. If so, that's your duplicate number - A.
Also, while iterating through the loop, add each number to the other, and get their sum (omitting the double occurrence of A). And since you have a series from 1..n,
sum(1..n) = n * (n + 1) / 2
So, the missing number is:
sum(1..n) - actual sum
edited Jun 28 at 17:20
Sam Onela
5,72961543
answered Jun 28 at 9:51
Sayan Bose
1111
The problem lies in these 2 lines of code:
for i in number_array:
if(number_array.count(i)==2):
Here for each number you are counting the number of occurrences in the array. Now, by doing that, You are reiterating over the numbers which are already counted. The call to number_array.count() searches the entire array, which means even for the last element, it will start from the first and calculate the count. This makes the time complexity $O(n^2)$. But, it can be done in $O(n)$ time.
Instead of using count, store the numbers in a hash table. And for each new number check, if it already exists in the hash table. If so, that's your duplicate number - A.
Also, while iterating through the loop, add each number to the other, and get their sum (omitting the double occurrence of A). And since you have a series from 1..n,
sum(1..n) = n * (n + 1) / 2
So, the missing number is:
sum(1..n) - actual sum
edited Jun 28 at 17:20
Sam Onela
5,72961543
answered Jun 28 at 9:51
Sayan Bose
1111
edited Jun 28 at 17:20
Sam Onela
5,72961543
edited Jun 28 at 17:20
Sam Onela
5,72961543
edited Jun 28 at 17:20
Sam Onela
5,72961543
5,72961543
answered Jun 28 at 9:51
Sayan Bose
1111
answered Jun 28 at 9:51
Sayan Bose
1111
answered Jun 28 at 9:51
Sayan Bose
1111
1111
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f197163%2ffinding-repeat-and-missing-numbers-in-an-array%23new-answer', 'question_page');
);
Post as a guest
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
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
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
I don't have time to write a full answer, but it comes down to this: you have a turned an O(n) problem into an O(n^2) problem. Here is the algorithm I would use: create a list of bools that is the size of
number_array. Initialize the elements to false with a list comprehension. Now, iterate throughnumber_array. For each number found, check the value in the bool list at that index - 1. If it's true, add that number to the output list. If it's false, set it to true. Then iterate through the list of bools. Once you find an element that is false, add the index of that element + 1 to the...– Mike Borkland
Jun 24 at 15:51
output list. Break from the loop and return the output list.
– Mike Borkland
Jun 24 at 15:51
1
Did you do some research? Various more efficient methods are demonstrated for example at geeksforgeeks.org/find-a-repeating-and-a-missing-number and stackoverflow.com/questions/5766936/…. – And here is another CR question about the same problem codereview.stackexchange.com/questions/194379/…
– Martin R
Jun 24 at 16:05
1
@MartinR my bad, I should have checked.
– Prathu Baronia
Jun 24 at 16:16
I actually solved by having an empty hashmap and started populating it as I proceeded and had a check on whenever the value goes to 2
– Prathu Baronia
Jun 28 at 11:45