How recursion terminate in array

Assignment Help Programming Languages

Reference no: EM1368467

A majority element in an array, A, of size N is an element that appears more than N/2 times (thus, there is at most one). For example, the array 3, 3, 4, 2, 4, 4, 2, 4, 4 has a majority element (4), whereas the array 3, 3, 4, 2, 4, 4, 2, 4 does not. If there is no majority element, your program should indicate this. Here is a sketch of an algorithm to solve the problem:

First, a candidate majority element is found (this is the harder part). This candidate is the only element that could possibly be the majority element. The second step determines if this candidate is actually the majority. This is just a sequential search through the array. To find a candidate in the array, A, form a second array, B. Then compare A1 and A2. If they are equal, add one of these to B; otherwise do nothing. Then compare A3 and A4. Again if they are equal, add one of these to B; otherwise do nothing. Continue in this fashion until the entire array is read. Then recursively find a candidate for B; this is the candidate for A (why?).

a. How does the recursion terminate?

b. How is the case where N is odd handled?

Reference no: EM1368467

Questions Cloud

Calculate net present value of benefits : Corporation A is planning the purchase of a new machine that would lower cash outflow. The cost of the machine is 30,000. The annual reduction in cash flows is:

Draw a proposed catalytic cycle : Draw the enantiomer of proline which would give rise to the absolute stereochemistry and draw a proposed catalytic cycle for the transformation and how does the catalyst activate the substrate

Write problems and issues associated with internet databases : Over 70% of web applications use database to store persistent data. Write some of the problems and issues associated with internet databases?

Strategy for internalizing positive externalities : Some real estate economists have argued that anchor stores in shopping malls create significant externalities for overall sales.

How recursion terminate in array : Continue in this fashion until entire array is read. Then recursively determine a candidate for B; this is candidate for A (why?). How does the recursion terminate?

Question on opportunity cost : Think about the trade off in work and leisure during a given day, and from day to day. During a given day, does opportunity cost of work rise, decline, or remain constant with each additional hour of work?

Explain the managers will e-mail their weekly reports : Explain The managers will e-mail their weekly reports to you on Monday of the following week and You will then produce the summary report. Explain the process for doing this and Give a sample formula to total the number of mini-gizmos produced by ..

Describe why analyst needs to understand how people think : Describe why an analyst requires to understand how people think, how they learn, how they react to change, how they communicate, and how they work.

Explain and contrast the dynamics between dominant cultures : Explain and Contrast the dynamics between dominant cultures and subcultures either in a work setting or in society.

User Account

All Pages