# PROBLEM LINK:

* Author:* Anjali Jha

*Sunita Sen*

**Tester:**# DIFFICULTY:

EASY

# PREREQUISITES:

None

# PROBLEM:

There are N integers in an array. The elements follow the below rules:

- The number of unique integers in the array lies in the range L to R (both inclusive).
- Every element in the array is either 1 or x, in which case x/2 is also definitely present in the array.

The maximum and minimum sum of all elements of the array needs to be printed which satisfies the above constraints.

# EXPLANATION:

All the elements will surely be powers of 2 and only then rule 2 can be satisfied.

To find the minimum sum of elements, there must be at least L unique integers. Therefore, we add 2^{k} to min, where 0 \leq k \leq L-1. After satisfying the constraint of adding L unique integers, we are left with N-L integers. The smallest possible number which can be present in the array is 1. Hence we add (N-L)*1 to min.

To find the maximum sum of elements, there must be maximum R unique integers. So we add all 2^{k} to max, where 0 \leq k \leq R-1. After satisfying the constraint of adding R unique integers, we are left with N-R integers. The biggest possible number which can be present in the array is 2^{R-1}. Hence we add (N-R)*2^{R-1} to max.

For example, given N=5, L=2, L=4.

There must be at least 2 unique integers. Therefore, add 2^{0} and 2^{1} to min. Remaining 3 elements must be 1 to make the sum minimum. Therefore, min=1+2+1+1+1.

There must be maximum of 4 unique integers. Therefore, add 2^{0}, 2^{1}, 2^{2} and 2^{3} to max. Remaining 1 element must be 2^{3} to make the sum maximum. Therefore, max=1+2+4+8+8.

# TIME COMPLEXITY:

The time complexity will be **O(log N)**

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define ll long long
using namespace std;
void solve() {
int n,l,r;
cin>>n>>l>>r;
int x=pow(2,l-1);
int y=pow(2,r-1);
int mn=0,mx=0;
while(x) {
mn+=x;
x=x/2;
}
mn+=(n-l);
int k=1;
while(k<=y) {
mx+=k;
k*=2;
}
mx+=(n-r)*y;
cout<<mn<<" "<<mx<<endl;
}
int main(){
ios ::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
```