Odd Array (Codblnd2)

Problem Link Practice
Author : Ankur Pandey
Difficulty
Easy
Explanation : One of the approaches to solve this question is to remove the duplicates from the array by inserting them into the set (Data Structure). Start dividing and count the numbers that are even and largest from the set by 2 and again insert them into the set. We will continue this operation until there is no element in the set.

Why does this work ?

Doing operation on a single element is the same as on repeated elements because we have to select the element which has the same value in the array and divide them by 2. In order to reduce the number of operations and elements we avoid duplicate elements. We start from largest because if we reduce the larger one by dividing by 2, so that it would be equal to the elements that are in the set which again reduces duplicates.

Sample Input :-
6
40 6 40 3 20 1

Sample Output :-

4 Explanation of Sample Input :-

If we insert the elements into the set then the resultant set would be {1,3,6,20,40}.

  1. We pick the largest and even number from the set i.e 40 and divide it by 2 and so insert 20 into the set. Resultant set would be {1,3,6,20}. Since duplicates are not allowed in set , 20 appears only once in set.
  2. We pick the largest and even number from the set i.e 20 and divide it by 2 and insert into the set. Resultant set would be {1,3,6,10}.
  3. We pick the largest and even number from the set i.e 10 and divide it by 2 and insert into the set. Resultant set would be {1,3,5,6}.
  4. We pick the largest and even number from the set i.e 6 and divide it by 2 and insert into the set. Resultant set would be {1,3,5}.

Since, there are no even numbers in the set we just remove them from the set. In Total there are 4 operations.

Code

void code(){
int n; cin>>n;
set s;
for(int i=0; i<n; i++) {
int x; cin>>x;
if(!(x&1))s.insert(x);
}

int cnt = 0;
while(!s.empty()) {
    int ele = *s.rbegin();
    s.erase(ele);

    if(!(ele%2)) {
        s.insert(ele/2);
        cnt++;
    }
}
cout<<cnt<<endl;

}