s1.shubham
BAN USERWe can do it in O(log N ^ 2) , the idea is :
Square(x) = Square(x-1) + 1 + (x-1)*2 when x is odd,
Square(x) = Square(x/2) * 4 when x is odd,
As we can see the multiplication term is so small that we can write them as sum.
Now we can binary search for the answer simply using this function
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL rec(LL x)
{
if(x<=1)return x;
if(x&1){
LL y = rec(x-1);
return 1 + y + x-1 + x-1;
}else{
LL y = rec(x/2);
return y + y + y + y;
}
}
LL sqt(LL x)
{
LL L = 0 , R = 1e9 , M ;
while(L<R){
M = (L+R+1)/2;
if(rec(M)<x)L = M ;
else R=M-1;
}
return rec(L+1)==x;
}
int main()
{
cout<<sqt(1)<<"\n";
cout<<sqt(2)<<"\n";
cout<<sqt(3)<<"\n";
cout<<sqt(4)<<"\n";
cout<<sqt(25)<<"\n";
cout<<sqt(26)<<"\n";
return 0;
}
Let the numbers be a , b , c from A , B , C .
- s1.shubham July 16, 2016Then let's sort them and lets denote them by x1 < x2 < x3.
Then ,
Our function is 2 * (x3-x1) which is nothing but range of the three elements.
The question can be re stated as find the minimum range such that there exists an element from each array. This can be solved using a heap .