Given a number having only one ’1′ and all other ’0′s in its binary representation, find position of the only set bit:
Ex- Input 2,4,8,9
Output 2,3,4, -1 Respectively.
//I did it by using Binary Search,Because i couldn't find better approach than this.... Here is my program. Complexity is logk.
#include<iostream>
using namespace std;
int PowerofTwo(long int n)
{
return n&&(!(n&n-1));
}
int setBit(long int n)
{
if(!PowerofTwo(n))
return -1;
long int mid,left,right;
left=0,right=31;
long int k=1;
int temp=1;
while(k)
{ mid=(left+right)/2;
k=1<<mid;
if(k<n)
{
left=mid;
}
else if(k>n)
{
right=mid;
}
else
{
return mid+1;
}
}
}
int main(void)
{ long int N=32768; // Input data.....change it for check on different numbers
cout<<setBit(N)<<endl;
return 0;
}
Ex- Input 2,4,8,9
Output 2,3,4, -1 Respectively.
//I did it by using Binary Search,Because i couldn't find better approach than this.... Here is my program. Complexity is logk.
#include<iostream>
using namespace std;
int PowerofTwo(long int n)
{
return n&&(!(n&n-1));
}
int setBit(long int n)
{
if(!PowerofTwo(n))
return -1;
long int mid,left,right;
left=0,right=31;
long int k=1;
int temp=1;
while(k)
{ mid=(left+right)/2;
k=1<<mid;
if(k<n)
{
left=mid;
}
else if(k>n)
{
right=mid;
}
else
{
return mid+1;
}
}
}
int main(void)
{ long int N=32768; // Input data.....change it for check on different numbers
cout<<setBit(N)<<endl;
return 0;
}
// Happy Coding
Suggest me if there is another better approach.
No comments:
Post a Comment