Xyron10's blog

By Xyron10, history, 20 months ago, In English

For an array of n integers, the following operation can be performed on it any number of times: - Consider m to be the current size of the array arr. Then, k(1 <= k <= m) elements from the array with positions x1 , x1 , ...... xk can be removed from the array if 2^arr[x1] + 2^arr[x2] + ...... + 2^arr[xk] = 2^p for some non-negative integer p.

Given an array arr of n integers, find the minimum number of operations required to remove all elements from the array.

Example-

Consider n=5, arr = [1, 1, 3, 2, 3]. The following 2 operations can be performed to make the array empty: - In the first operation, remove arr, arr2 arr4, as their sum is 2^1+2^1+2^8 = 8 which is 2^3. Now, arr becomes [3,3]. - In the second operation, remove arr1, and arr2 as their sum is 2^3 +2^3 = 2^4. Now, arr becomes empty.

Hence, the answer is 2. It can be shown that the answer cannot be less than 2.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

solution of the problem in cpp

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
int main()
{
   int n;
   cin>>n;
   int arr[n];
   for(int i=0;i<n;i++)
   {
       cin>>arr[i];
       arr[i]=pow(2,arr[i]);
   }
   sort(arr,arr+n);
   stack<int> st;
   for(int i=0;i<n;i++)
   {
       while(!st.empty() && st.top()==arr[i])
       {
           arr[i]+=st.top();
           st.pop();
          
       }
        st.push(arr[i]);
   }
   cout<<st.size();

    return 0;
}