AITC2G14 - Editorial

editorial
1

PROBLEM LINK:

Practice

Contest Link:

Setter: Rahul Kumar

Tester: Rahul Kumar

Editorialist: Anushwar Sharma

DIFFICULTY:

Simple

PREREQUISITES:

Basic observations, Array.

PROBLEM:

An Imaginary machine that takes input in a binary number system and shuffles the digits (without changing the total no. of 1s and 0s) and gives the output by changing the number into a decimal number system.
Given an array of size N containing 0s and 1s.
Your task is to calculate the smallest possible decimal no. that can be formed after shuffling.

EXPLANATION

Observe that the minimum number can be formed by 0s and 1s is only when all zeros are at the beginning. All the zeros at the beginning can be removed as it does not affect the number. So you have to count the number of 1s and that will contribute to the minimum decimal number.
Now you can convert the binary number into decimal no. To do that you can run a loop for all the ones and calculate the power of two 2^0+2^1+2^2… up to no. of 1s, or the more optimized way is, as we have only 1s in the binary number so the decimal number will be always 2^(n-1)-1 by observation. For e.g, Binary no. 1111 is 7 in decimal, there are four 1s so 2^(4-1)-1 is also 7.

SOLUTION:

Editorialist's Solution 
#include<bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define vi vector<int>
#define w(x) int x; cin>>x; while(x--)
#define pb push_back 

int32_t main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif   
    
    int t;
    cin>>t;
    while(t--)
    {
        int n,s=0;
        cin>>n; vi v;
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x; v.pb(x);
            if(x==1)
                s++;
        }
        int ans =pow(2,s)-1;
        cout<<ans<<"\n";
    }
}

Note: If you are a beginner, don’t be scared of the few lines that have been written at the top. Just focus on the code starting from the variable declaration and if you don’t understand any shorthand terminology mentioned in the code, look at the top “#define”, where we have defined all the constants used in the code.

Feel free to share your approach, if you want to(even if it’s the same). Suggestions are welcomed as always had been. :slight_smile: