DO not use for or while. Any looping must be accomplished using recursion.

Part 3a. Largest power of two less than

Implement the method public static int lp2lt(int n) which calculates and returns the

largest integer power of 2 less than n. You may assume n is greater than 1. For example, if n is 10, the

largest power of 2 less than n is 8 (8 is 2 cubed). If n is 8, the answer is 4. If n is 2, 20 = 1.

Part 3b. There can be only one

You are holding a contest to determine the ultimate penny champion. Each participant in the contest has decided which side of the penny they like, heads or tails, and keeps that decision to themselves. We

represent heads using the boolean value true and tails using false. The contest participants all get in

a long line (array). They start by pairing up (the first two, second two, and so forth). After the two

members reveal their pennies to each other (battle), if they are different boolean values, the first (left)

person wins, otherwise, the second (right) person wins. There are no draws/ties. The battles are single

elimination: once a participant loses, they stop playing in the contest. The remaining members then

battle it out the same way in the next round (first winner of the first round battles the second winner of

the first round, third winner of the first round battles the fourth winner, etc.). Battle rounds continue to

occur in this way until only one winner emerges. If there are an odd number of people in any round, the

last person gets a "bye" and automatically survives to the following round.

It should return the index corresponding to the winner of the contest. You do not need to allocate any

arrays for this problem and you should not modify the input array as it contains the decisions that the

participants have made, which never change. Instead, adapt what we learned from binary search. You

will probably need a helper method. You may assume that the array is at least length 1.

Note: It can be proven that the above problem is equivalent to dividing up the line of participants into

two parts (where each part is a contiguous "piece" of the line), performing a totally separate

champion contest for each part, and having the winners of the two separate contests pairing up for a

final match. The length of the first part is the largest power of two less than the number of

participants, and the second part is the remaining participants. (Part 3a will help!)

For example, if there are 11 participants, you would divide into a contest of the first 8 participants

followed by a contest of the other 3. The 3 participants would have a pair battling with the other in a

bye. The winner of the faceoff between the pair winner and the bye would survive until the final battle!

See if you understand how this version of the problem results in the same sequence of battles that

would occur in the earlier description.

public static int champion(boolean[] a){

write code here

}