CODEWITHSUNDEEP
algorithmfunction
user1108765
user1108765

Reputation: 113

Finding even numbers in an array

Given an array of length n containing at most e even numbers and a function isEven 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 isEven.

The only thing I could think was to do a linear search and stop after I hit the end of the array or found e even numbers. Can someone please tell me a better way?

Upvotes: 9

Views: 2390

Answers (1)

PengOne
PengOne

Reputation: 48398

You can do a binary search instead. Write a function that does the following:

  • Start with A = array and n = length(A).
  • While n>1
    • Set L = [A[0],A[1],...,A[k-1]] and R = [A[k],A[k+1],...,A[n-1]] where k = floor(n/2)
    • If isEven(product of elements of L), then set A=L and n = k,
    • Otherwise set A=R and n = n-k.
  • If isEven(A[0]), return A[0],
  • Otherwise, return -1.

Run a for loop that will have at most e iterations. Each time run the algorithm above to find an even number, if the output is -1 stop, there are no more to find. Otherwise, print the output, remove it from the array, and iterate for at most e trials.

The binary search algorithm takes log(n) calls to isEven, and you must run it at most e times, so there are a total of e log(n) calls to isEven.

Therefore you want to take this approach whenever e log(n) < n, otherwise use the linear search, which takes n calls to isEven.

Upvotes: 16

Related Questions