-1
$\begingroup$

Lets assume we have an array with 100 numbers and we want to find how many '1's there are. Best solution will be reading every numbers and counting. Now we get a hint that there are 50,51 or 52 '1' in the array, can this information help us count the '1's somehow?

What bothering me here is that we have a lot of information about the array but it still doesn't appear to help the find the amount of '1's.

$\endgroup$
1
$\begingroup$

Assume that someone hints you there are 50,51 or 52 '1's then as a first optimization (memory wise) you may want to use a 2-bit counter and count $\mod 3$. That said, you'll still need to go over the entire array to get the right answer in the worst-case)- assume you read 99 entries and found 51 '1's. How can you tell if there are 51 '1's or 52, without reading the last number?

$\endgroup$
  • $\begingroup$ that's an interesting memory optimization, but i guess its the same as if your hint was the range, we still didn't use the fact that the range starts with 50 $\endgroup$ – Vladp Jan 12 '15 at 13:15
  • $\begingroup$ @Vladp - In the worst case, you can't solve it using less than 2-bits of memory or reading all of the array by a simple diagnolization argument, so this is optimal.. $\endgroup$ – R B Jan 12 '15 at 13:18
  • $\begingroup$ what is the diagnolization argument? $\endgroup$ – Vladp Jan 12 '15 at 13:23
  • $\begingroup$ @Vladp - assume there's an algorithm which uses less than 2 bits of memory, then it must reach the same configuration for two of $50,51,52$ (pigeonhole principle), thus it can not be correct for any input. As for the need to read all of the integers, see a similar argument proof here. $\endgroup$ – R B Jan 12 '15 at 13:35
1
$\begingroup$

In the worst-case, (maybe by an adversary argument), you still have to check all the numbers to determine the number of $1$.

A possible optimization: if you are really lucky that you have encountered 52 $1$s [or 50 $\lnot 1$s (not $1$)] before reaching the end of the array, you can conclude that there are totally 52 [or 50] $1$s in the array.

$\endgroup$
  • $\begingroup$ its true but what is we have 1M array with 1s being from 1000 to 2000, cant get lucky here $\endgroup$ – Vladp Jan 12 '15 at 13:40
0
$\begingroup$

Looking at your example first let's assume that what you mean by 'approximation' in your title question is to have some knowledge for the solution but not the full solution (which comes either by means of approximation or other means).

So, yes, having some knowledge about the solution does help us find the exact answer. Here is how and why using your example.

Knowing nothing about the solution would have us as you say look at all 100 elements to count 1's. But knowing that the 1's are either 50, 51 or 52 in the case of 52 we do not have to read all 100 elements, we can stop at the 52nd 1 found without checking any further elements. This helps us because it improves our overall average complexity to reading 92.32 elements instead of 100.

So, in conclusion, while having some knowledge about the solution does not provide any help using worst case complexities (i.e. considering the worst input case scenario) it does provide help generally i.e. when considering each input as likely or in the average case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.