Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 344
user1108765 Avatar asked Dec 20 '11 22:12

user1108765


People also ask

How do you filter an even number in an array?

To filter even numbers of an integer Array in JavaScript, call Array. filter() method on this integer array, and pass a function as argument that returns true for an even number or false otherwise. filter() method returns an array with elements from the original array that returns true for the given callback function.

How do you check if an array is even or odd?

Use modulus operator to check if the number is even or odd. If we divide any number by 2 and reminder is 0 then the number is even, otherwise it is odd. Save this answer.

How do you find the even number?

All the numbers ending with 0, 2, 4, 6 and 8 are even numbers. For example, numbers such as 14, 26, 32, 40 and 88 are even numbers. If we divide a number into two groups with an equal number of elements in each, then the number is an even number.


1 Answers

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.

like image 170
PengOne Avatar answered Oct 21 '22 12:10

PengOne