Help regarding time complexity difference

, ,
1

I am confused as to what data types has to do with the time complexity of a solution.
I came across a problem:
Problem link: CodeChef: Practical coding for everyone

Solution which got TLE:-
#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
int a;int b;cin>>a>>b;
int temp=a;
int ans=0;
while(temp<=b)
{
ans++;
temp=temp*2;
}
cout<<ans;
return 0;
}

solution which got accepted:

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
double a,b;
cin>>a>>b;
double ans=0,temp=a;
while(temp<=b){
ans++;
temp*=2;
}
cout<<ans;
return 0;
}

Please throw some insights as to how these solutions vary in terms of time complexity.

2

Anyone can find the logic behind the TLE?

3

Long long is slower as it requires more bits

4

@dhruv788 ,even after changing the data type to int ,it gives TLE.Only in case of double it is getting the solution accepted. Whats the logic behind this?
I have attached the problem link in the parent thread,test it out

5

https://www.codechef.com/viewsolution/46755139
using long long and float will also work

6

It’s easy to see how to make a solution like e.g. this one TLE:

1111 2147483647

but I can’t see how you’d do it with e.g. this (note the - shudder - #define int long long), assuming of course that the constraints are correct (a fairly big assumption, as it’s a third-party contest and they didn’t manage to render them in LaTeX properly XD).

Edit:

Maybe someone should do a submission where they assert that 1 \le A \le B \le 10^{18}.

7

@akshay_012 my doubt is why does simple int gives TLE and float doesn’t?

8

@ssjgz Even if we assume range of A and B to be within limits,why does int gives TLE and double gives AC.
Any logic behind that?

9

Run the test input with the int solution (CodeChef: Practical coding for everyone) and find out :slight_smile:

Hint:

Print the value of res for each iteration of the loop.

10

still didn’t get ur point,can u please elaborate what test input u have used and whats the point u r trying to make by it?

11

Try it and see :slight_smile: