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.
solution of the problem in cpp