Can anyone tell me what is time complexity of below code and How to calculate?

Problem
(Contest Page | CodeChef)
My Code

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define lli long long int
#define vi vector<lli>
#define pb push_back
#include<string>
#define mp map<string,lli>
#define mpp map<lli,lli>
#define MP map<char,lli>
#define SS set<lli>
#define pq priority_queue<lli>
#define F first
#define S second
#define YES cout<<"YES\n";
#define NO cout<<"NO\n";
#define mod 1000000007
#define test lli t;cin>>t;while(t--)
using namespace std;
/*
bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second > b.second);
}
*/
lli present(lli x)
{
    lli cnt=0;
    while(x%2==0)
    {
        x=x/2;
        cnt+=1;
    }
    return cnt;
}
int main()
{
    test
    {
        lli n,odd=0;
        cin>>n;
        vi arr(n,0);
        for(lli i=0;i<n;i++)
        {
            cin>>arr[i];
            if(arr[i]%2!=0)
                odd+=1;
        }
        if(odd>=1)
            cout<<0<<endl;
        else
        {
            lli val=INT_MAX;
            for(lli i=0;i<n;i++)
            {
                lli cnt=present(arr[i]);
                val=min(val,cnt);
            }
            cout<<val<<endl;
        }
    }
}
 and 

Time Complexity of present() function is O(\log_2{}N). Therefore, time complexity of whole code is O(N\log_2{A_{max}}).

You should also make sure A_i \gt 0. present() function will run forever for A_i \ge 0.

1 Like