i am doing a question in which i have to remove elements of odd indices repetative until there is only one element in array . i know many of you know about that question . i dont need the solution code i just want to know how to find no of elements of array
they explained it in very detail hope it helps.
Here’s what you want.
Give it a thought:
I would like to formally define a sequence first:
A sequence is a function from the set of natural numbers (can sometimes include zero) into some other set, say A. The images are often called the elements of the sequence. So given any natural number in the domain of the sequence (finite or infinite), we can find the element just like we find the value of any other function at some point in its domain. The image of a natural number would be unique, that is, we won’t be having multiple values for the second or the third element for example.
Let’s say it’s the i-th operation of the given type (one operation corresponding to removing every element mapped by an odd index) being applied to an array (that holds those elements). Forget about the actual elements for a moment and just think of applying the operation on the indices (for we can always map the last index that remains to the corresponding element in the array: remember the uniqueness of the images). What can you say about the first two indices at this point (i-th iteration)?
Okay, let’s start from the very first operation (i=1). Before the operation, the indices are:
1, 2, 3, …
Notice the first two elements are the powers of two (2^0=1, 2^1=2). Now when we apply the operation, we are removing the odd indices: so the first element (inherently odd) will always get removed and second (inherently even) won’t. So, 2^0 isn’t going any further. Now before second operation (i=2), the remaining indices are:
2, 4, 6, …
You must have guessed the pattern by now. Before any i-th operation, the first remaining index will be 2^(i-1) and the second will be 2^i. Generally, all subsequent indices will be multiples of the first in order. This operation will remove 2^(i-1) along with all its odd-multiples and will pass 2^i and its multiples onto the next operation.
In the end, there will be only one index left (trivially the first after the last operation). From the established invariant, this number is a power of two. And not just any power, the highest power of two that was in the sequence (1, 2, 3, …) originally.
To find that, you just take the floor of the logarithm of the number of elements (or the last index) in base 2 and then raise 2 to the result. Done. Say, the result is k: your final answer is at A[k].
The problem can be generalised to remove every b-th element. Only thing that changes is the base of the logarithm and exponentiation
bro i am using similar idea …i am about to finish .thanks a lot bro