Databases
StackOverflow2013
Postsdbo
POFinding even numbers in an array without using feedback
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFinding even numbers in an array without using feedback
    primarykey
    data
    text
    <p>I saw this post: <a href="https://stackoverflow.com/questions/8582959/finding-even-numbers-in-an-array/8584598">Finding even numbers in an array</a> and I was thinking about how you could do it without feedback. Here's what I mean.</p> <blockquote> <p>Given an array of length n containing at most <code>e</code> even numbers and a function <code>isEven</code> that returns true if the input is even and false otherwise, write a function that prints all the even numbers in the array using the fewest number of calls to <code>isEven</code>.</p> </blockquote> <p>The answer on the post was to use a binary search, which is neat since it doesn't mean the array has to be in order. The number of times you have to check if a number is even is <code>e log n</code> instead if <code>n</code> because you do a binary search (<code>log n</code>) to find one even number each time (<code>e</code> times). </p> <p>But that idea means that you divide the array in half, test for evenness, then decide which half to keep based on the result.</p> <p>My question is whether or not you can beat <code>n</code> calls on a fixed testing scheme where you check all the numbers you want for evenness without knowing the outcome, and then figure out where the even numbers are after you've done all the tests based on the results. So I guess it's no-feedback or blind or some term like that.</p> <p>I was thinking about this for a while and couldn't come up with anything. The binary search idea doesn't work at all with this constraint, but maybe something else does? Even getting down to <code>n/2</code> calls instead of <code>n</code> (yes, I know they are the same big-O) would be good.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USDaniel
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFinding even numbers in an array without using feedback
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFinding even numbers in an array without using feedback
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFinding even numbers in an array without using feedback
      1. USDaniel
      1. VTBountyStart
    1. COCould you please explain the binary search solution in more details? I somehow can't think of a way to use binary search here.
      singulars
      1. POFinding even numbers in an array without using feedback
      1. USIvaylo Strandjev
    2. CO@istrandjev look at this answer: http://stackoverflow.com/a/8584598/661284
      singulars
      1. POFinding even numbers in an array without using feedback
      1. USDaniel
    3. COThe linked answer is taking advantage of a loop-hole. It supposes that we're allowed to multiply numbers, and test the evenness of the product. If we can use arithmetic, we can craft our own evenness test (use integer division in `2 * (x / 2) == x`) and never call `isEven` at all.
      singulars
      1. POFinding even numbers in an array without using feedback
      1. USphs
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload