Reduce an array to one element using the given operation

Given an integer variable Number as input. Let us consider an array containing elements in the range 1 to Number in sorted order. If we perform an operation on an array, elements at odd positions will be removed at each step. Then the goal is to perform this operation N The number of times until there is only one element left. Print the element at the end.

Note -: The elements are positioned so that the array at index 0 is at position 1, and so on.

Test case for the number of elements in the array

Input number=1, output=1

Input number=2, output=2

Input number =3, output=2

>

Input quantity=4, output=4

Input quantity=5, output=4

Input quantity=6, output=4

Input quantity=7, output=4

...

Input quantity=12, output=8

Input quantity=20, Output = 16

Based on the above observation, for the range of numbers between 2ⁱ to 2^{i 1}-1, the output will be 2ⁱ .

Example

Input−Number=7

Output− The elements after a single reduction operation are: 4

Explanation− The first element is at position 1, and so on.

The array will be [ 1 2 3 4 5 6 7 ]

After the first operation: [ 2 4 6 ]

After the second operation: [ 4 ]

Input − Number=18

Output− The single element after the reduction operation is: 4

Explanation − The first element is at position 1 and the

array will be [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ]

first After the 2nd operation: [ 2 4 6 8 10 12 14 16 18]

After the 2nd operation: [ 2 8 12 16 ]

After the 3rd operation: [ 8 16 ]

After the 4th operation [16]

The method used in the following program is as follows

In this method, we will use a while loop to calculate the final result based on the above formula . Starting with an initial value of 2, iterate until 2*result

• Get the input variable Number

• Function getsingleElement(long num) Gets the input number and prints the result according to the above formula.

• Get variable results.

• Initialize the result with 2.

• Use a while loop to traverse until the result *2 li>

• will double the result.

• Once the while loop ends, we get the desired value.

Return results.

• Print the results in main.

Example

#include<bits/stdc++.h>
using namespace std;
long getsingleElement(long num){
   long result;
   result=2;
   while(result*2 <= num){
      result=result*2;
   }
   return result;
}
int main(){
   int Number = 20;
   cout<<"The single element after reduction operation is : "<<getsingleElement(Number) ;
   return 0;
}

Output

If we run the above code it will generate the following output

The single element after reduction operation is : 16

The above is the detailed content of Reduce an array to one element using the given operation. For more information, please follow other related articles on the PHP Chinese website!