Mixing
Outputting numbers within a range that are not in a list
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated list of 100 integers?
The aim is to output the number of such integers, and determine if the randomly generated list of 100 integers included any repeats.
The naive approach would be to compare each number from 0 to 255 against the list of 100 integers. This would not be very efficient.
What would be a more efficient approach to solve this?
algorithms
asked 5 hours ago
sortedquick
61
New contributor
sortedquick 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 |Â
up vote
1
down vote
favorite
How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated list of 100 integers?
The aim is to output the number of such integers, and determine if the randomly generated list of 100 integers included any repeats.
The naive approach would be to compare each number from 0 to 255 against the list of 100 integers. This would not be very efficient.
What would be a more efficient approach to solve this?
algorithms
asked 5 hours ago
sortedquick
61
New contributor
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
Honestly, if you really only have 100 integers in the list and they're really only between 0 and 255, there's probably not much point trying to optimize this. For such a small task, any algorithm that works will be adequate, unless you need to run it many, many times.
– David Richerby
5 hours ago
So if you use one bit per value (256), in one loop set bit for each integer, output that value if the bit is set and then in second pass output values for bits that are 0, is it sufficient?
– Evil
4 hours ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated list of 100 integers?
The aim is to output the number of such integers, and determine if the randomly generated list of 100 integers included any repeats.
The naive approach would be to compare each number from 0 to 255 against the list of 100 integers. This would not be very efficient.
What would be a more efficient approach to solve this?
algorithms
asked 5 hours ago
sortedquick
61
New contributor
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated list of 100 integers?
The aim is to output the number of such integers, and determine if the randomly generated list of 100 integers included any repeats.
The naive approach would be to compare each number from 0 to 255 against the list of 100 integers. This would not be very efficient.
What would be a more efficient approach to solve this?
algorithms
algorithms
asked 5 hours ago
sortedquick
61
New contributor
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
sortedquick
61
New contributor
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
sortedquick
61
New contributor
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 5 hours ago
sortedquick
61
asked 5 hours ago
sortedquick
61
61
New contributor
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
Honestly, if you really only have 100 integers in the list and they're really only between 0 and 255, there's probably not much point trying to optimize this. For such a small task, any algorithm that works will be adequate, unless you need to run it many, many times.
– David Richerby
5 hours ago
So if you use one bit per value (256), in one loop set bit for each integer, output that value if the bit is set and then in second pass output values for bits that are 0, is it sufficient?
– Evil
4 hours ago
add a comment |Â
1
Honestly, if you really only have 100 integers in the list and they're really only between 0 and 255, there's probably not much point trying to optimize this. For such a small task, any algorithm that works will be adequate, unless you need to run it many, many times.
– David Richerby
5 hours ago
So if you use one bit per value (256), in one loop set bit for each integer, output that value if the bit is set and then in second pass output values for bits that are 0, is it sufficient?
– Evil
4 hours ago
1
1
Honestly, if you really only have 100 integers in the list and they're really only between 0 and 255, there's probably not much point trying to optimize this. For such a small task, any algorithm that works will be adequate, unless you need to run it many, many times.
– David Richerby
5 hours ago
Honestly, if you really only have 100 integers in the list and they're really only between 0 and 255, there's probably not much point trying to optimize this. For such a small task, any algorithm that works will be adequate, unless you need to run it many, many times.
– David Richerby
5 hours ago
So if you use one bit per value (256), in one loop set bit for each integer, output that value if the bit is set and then in second pass output values for bits that are 0, is it sufficient?
– Evil
4 hours ago
So if you use one bit per value (256), in one loop set bit for each integer, output that value if the bit is set and then in second pass output values for bits that are 0, is it sufficient?
– Evil
4 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $O(1)$.
Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.
let found be an array [0..255]
found ↠[false, false, false...]
for i ↠[1..100]:
value ↠A[i]
if found[value] is true:
there was a repeat
found[value] ↠true
for j ↠[0..255]:
if found[value] is false:
j was not in the list
This runs in $O(n+k)$ time and $O(k)$ space (where $n$ is the number of elements in the array and $k$ is the maximum size of those elements). I don't believe it's possible to do better.
answered 3 hours ago
Draconis
2,815514
add a comment |Â
up vote
1
down vote
Let $n$ be the number of random elements (in your case $n = 100$), and let $k$ be the total number of elements (in your case $k = 256$). Draconis gave a solution in time and space $O(k)$.
Another possible solution uses time $O(nlog n + k)$ and space $O(n)$:
Sort the input elements $A[1],ldots,A[n]$.
Let $i gets 1$.
For $j gets 0,ldots,k-1$:
If $i > n$ or $A[i] neq j$: output $j$.
While $i leq n$ and $A[i] = j$: let $i gets i + 1$.
This is strictly better than the other solution if $n = o(k/log k)$.
answered 2 hours ago
Yuval Filmus
186k12176337
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $O(1)$.
Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.
let found be an array [0..255]
found ↠[false, false, false...]
for i ↠[1..100]:
value ↠A[i]
if found[value] is true:
there was a repeat
found[value] ↠true
for j ↠[0..255]:
if found[value] is false:
j was not in the list
This runs in $O(n+k)$ time and $O(k)$ space (where $n$ is the number of elements in the array and $k$ is the maximum size of those elements). I don't believe it's possible to do better.
answered 3 hours ago
Draconis
2,815514
add a comment |Â
up vote
3
down vote
Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $O(1)$.
Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.
let found be an array [0..255]
found ↠[false, false, false...]
for i ↠[1..100]:
value ↠A[i]
if found[value] is true:
there was a repeat
found[value] ↠true
for j ↠[0..255]:
if found[value] is false:
j was not in the list
This runs in $O(n+k)$ time and $O(k)$ space (where $n$ is the number of elements in the array and $k$ is the maximum size of those elements). I don't believe it's possible to do better.
answered 3 hours ago
Draconis
2,815514
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $O(1)$.
Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.
let found be an array [0..255]
found ↠[false, false, false...]
for i ↠[1..100]:
value ↠A[i]
if found[value] is true:
there was a repeat
found[value] ↠true
for j ↠[0..255]:
if found[value] is false:
j was not in the list
This runs in $O(n+k)$ time and $O(k)$ space (where $n$ is the number of elements in the array and $k$ is the maximum size of those elements). I don't believe it's possible to do better.
answered 3 hours ago
Draconis
2,815514
Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $O(1)$.
Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.
let found be an array [0..255]
found ↠[false, false, false...]
for i ↠[1..100]:
value ↠A[i]
if found[value] is true:
there was a repeat
found[value] ↠true
for j ↠[0..255]:
if found[value] is false:
j was not in the list
This runs in $O(n+k)$ time and $O(k)$ space (where $n$ is the number of elements in the array and $k$ is the maximum size of those elements). I don't believe it's possible to do better.
answered 3 hours ago
Draconis
2,815514
answered 3 hours ago
Draconis
2,815514
answered 3 hours ago
Draconis
2,815514
answered 3 hours ago
Draconis
2,815514
2,815514
add a comment |Â
add a comment |Â
up vote
1
down vote
Let $n$ be the number of random elements (in your case $n = 100$), and let $k$ be the total number of elements (in your case $k = 256$). Draconis gave a solution in time and space $O(k)$.
Another possible solution uses time $O(nlog n + k)$ and space $O(n)$:
Sort the input elements $A[1],ldots,A[n]$.
Let $i gets 1$.
For $j gets 0,ldots,k-1$:
If $i > n$ or $A[i] neq j$: output $j$.
While $i leq n$ and $A[i] = j$: let $i gets i + 1$.
This is strictly better than the other solution if $n = o(k/log k)$.
answered 2 hours ago
Yuval Filmus
186k12176337
add a comment |Â
up vote
1
down vote
Let $n$ be the number of random elements (in your case $n = 100$), and let $k$ be the total number of elements (in your case $k = 256$). Draconis gave a solution in time and space $O(k)$.
Another possible solution uses time $O(nlog n + k)$ and space $O(n)$:
Sort the input elements $A[1],ldots,A[n]$.
Let $i gets 1$.
For $j gets 0,ldots,k-1$:
If $i > n$ or $A[i] neq j$: output $j$.
While $i leq n$ and $A[i] = j$: let $i gets i + 1$.
This is strictly better than the other solution if $n = o(k/log k)$.
answered 2 hours ago
Yuval Filmus
186k12176337
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Let $n$ be the number of random elements (in your case $n = 100$), and let $k$ be the total number of elements (in your case $k = 256$). Draconis gave a solution in time and space $O(k)$.
Another possible solution uses time $O(nlog n + k)$ and space $O(n)$:
Sort the input elements $A[1],ldots,A[n]$.
Let $i gets 1$.
For $j gets 0,ldots,k-1$:
If $i > n$ or $A[i] neq j$: output $j$.
While $i leq n$ and $A[i] = j$: let $i gets i + 1$.
This is strictly better than the other solution if $n = o(k/log k)$.
answered 2 hours ago
Yuval Filmus
186k12176337
Let $n$ be the number of random elements (in your case $n = 100$), and let $k$ be the total number of elements (in your case $k = 256$). Draconis gave a solution in time and space $O(k)$.
Another possible solution uses time $O(nlog n + k)$ and space $O(n)$:
Sort the input elements $A[1],ldots,A[n]$.
Let $i gets 1$.
For $j gets 0,ldots,k-1$:
If $i > n$ or $A[i] neq j$: output $j$.
While $i leq n$ and $A[i] = j$: let $i gets i + 1$.
This is strictly better than the other solution if $n = o(k/log k)$.
answered 2 hours ago
Yuval Filmus
186k12176337
answered 2 hours ago
Yuval Filmus
186k12176337
answered 2 hours ago
Yuval Filmus
186k12176337
answered 2 hours ago
Yuval Filmus
186k12176337
186k12176337
add a comment |Â
add a comment |Â
sortedquick is a new contributor. Be nice, and check out our Code of Conduct.
sortedquick is a new contributor. Be nice, and check out our Code of Conduct.
sortedquick is a new contributor. Be nice, and check out our Code of Conduct.
sortedquick is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcs.stackexchange.com%2fquestions%2f99790%2foutputting-numbers-within-a-range-that-are-not-in-a-list%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
1
Honestly, if you really only have 100 integers in the list and they're really only between 0 and 255, there's probably not much point trying to optimize this. For such a small task, any algorithm that works will be adequate, unless you need to run it many, many times.
– David Richerby
5 hours ago
So if you use one bit per value (256), in one loop set bit for each integer, output that value if the bit is set and then in second pass output values for bits that are 0, is it sufficient?
– Evil
4 hours ago