Sign in to follow this  

Difficult computer science problem

This topic is 4084 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Does anyone know an algorithm that recieves an unknown amount of numbers(it stops when it recieves -1) and calculates how many of them are above the average without using an array, list, vector, stack, file ect.? Is it even possible?

Share this post


Link to post
Share on other sites
The term you are looking for is "constant space".

This problem is provably unsolvable in constant space. Assume for a moment that we have inserted all integers between 1 and (N-1) into the program. The last integer we insert can result in any number of integers between N/2 and (N-1) being lower than the average (we can insert, to this effect, any number between 0 and N²). Therefore, the program must store enough information to determine which of the N/2 possibilities is valid, which cannot be done for any N if we restrict ourselves to constant space.

Share this post


Link to post
Share on other sites
I'm assuming you can hold variables. Can't you have a variable that's initialised to zero. Then if the inputted number is greater than the average then increase the variable. If it's -1 then quit. Or have I missed an obvious problem?

Share this post


Link to post
Share on other sites
This sounds suspiciously like homework. All I'll say is that it can be solved within the constraints listed using a technique that teachers/professors love to set homework problems about.

EDIT: This does depend on the interpretation of the list of constraints.

Σnigma

Share this post


Link to post
Share on other sites
The obvious problem is that you need to know all the numbers to get the average.

It can be done if you iterated the sequence twice, once to find the average and again to count how many are higher. Without storing them, you'd have the input the whole sequence twice.

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
The obvious problem is that you need to know all the numbers to get the average.

It can be done if you iterated the sequence twice, once to find the average and again to count how many are higher. Without storing them, you'd have the input the whole sequence twice.


Ah, I misread it. I thought it was a given average as opposed to the average of the numbers inputted.

Share this post


Link to post
Share on other sites
Quote:
Original post by Enigma
This sounds suspiciously like homework. All I'll say is that it can be solved within the constraints listed using a technique that teachers/professors love to set homework problems about.

EDIT: This does depend on the interpretation of the list of constraints.

Σnigma


what is "interpretation of the list of constraints"?

Share this post


Link to post
Share on other sites
Quote:
Original post by Semion_N
what is "interpretation of the list of constraints"?


It is the interpretation of the ect (sic) in the OP's question. Does his question mean to rule out any memory storage (constant space solving, which is provably impossible)? Does his question mean to rule out only the standard imperative storage approaches (hinting at an easily expressed recursive solution)?

I've interpreted it as the first option, since a recursive solution technically uses a stack (unless it uses tail recursion, but then the problem becomes provably unsolvable again). If it's homework, then the recursive solution would be a good answer, though.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
So it's a constant-space constraint. There is no solution to your problem in constant space.


It's not impossible - it's trivial. Loop once over the input to find the average. Loop over the inout again to count how many inputs are bigger than the average.

Share this post


Link to post
Share on other sites
PHP variable variables and a similar naming convention :D

${"name$num"}

Not an array, it's a series of regular variables, but it acts as one. ;)

Alright, alright, that was terrible, I apologize.

Share this post


Link to post
Share on other sites
Quote:
Original post by Bander
If I understand the problem specification then it is not trivial, the input is not given all at once for processing.


Quote:

recieves an unknown amount of numbers(it stops when it recieves -1)


That's actually pretty vague.

I assumed that the function would be something like void algorithm(int* input); and you'd iterate over the input array until you found a -1.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
...
Assume for a moment that we have inserted all integers between 1 and (N-1) into the program. The last integer we insert can result in any number of integers between N/2 and (N-1) being lower than the average ...


If negative numbers are allowed in the input then you could affect the status of ANY number of elements, not just [n/2, n-1].

Quote:
Original post by Nitage
Quote:
Original post by ToohrVyk
So it's a constant-space constraint. There is no solution to your problem in constant space.


It's not impossible - it's trivial. Loop once over the input to find the average. Loop over the inout again to count how many inputs are bigger than the average.


But to store the input in order to loop over it again will require more than constant space.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nitage
It's not impossible - it's trivial. Loop once over the input to find the average. Loop over the inout again to count how many inputs are bigger than the average.


This requires the input being given to you again (you cannot store it, because it's not constant in size). If you will, you can liken the input to an oracle which gives you integers.

If you have access to the entire set of integers as a memory portion, then memory is pretty obivously not constant.

Share this post


Link to post
Share on other sites
Using the languages built-in stack should not violate that constant memory restriction: That memory is already allocated, and when it runs out you get an overflow. The amount of memory in use remains constant.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by Nitage
It's not impossible - it's trivial. Loop once over the input to find the average. Loop over the inout again to count how many inputs are bigger than the average.


This requires the input being given to you again (you cannot store it, because it's not constant in size). If you will, you can liken the input to an oracle which gives you integers.


You've assumed all that - none of it is the problem description.

Quote:

If you have access to the entire set of integers as a memory portion, then memory is pretty obivously not constant.


If the algorithm itself allocates a fixed amount of memory, it runs using constant memory, regardless of how much memory was used to create any inputs to that algorithm.

Share this post


Link to post
Share on other sites
Quote:
Original post by Deyja
Using the languages built-in stack should not violate that constant memory restriction: That memory is already allocated, and when it runs out you get an overflow. The amount of memory in use remains constant.


The memory might not already be allocated - IIRC although windows has a fixed size stack per process, Linux can and will grow the stack as needed. We might (theoretically) only have a stack deep enough for one or two function calls.

Although I personally like the recursion solution, IMHO the question is too vauge to be useful or valid.

Share this post


Link to post
Share on other sites
Using the stack is not a solution. Regardless of whether the memory is pre allocated, the storage requirements of a recursive solution are a function of the size of the input and not a constant.

Share this post


Link to post
Share on other sites
A constant-space solution is a solution that can use the same amount of memory to solve every instance of the problem.

That a program allocates the same amount of memory for the stack each time is irrelevant. If the program runs out of that "constant memory," it will not work, and so it is not a solution of the problem.

For 10,000 numbers, you'll need more memory than you will for 100 numbers, so generally the solution needs more than constant memory.

Share this post


Link to post
Share on other sites

This topic is 4084 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this