Find Position Of Set Bit Geeks For Geeks
Problem Link:
(It is also the problem of the day for 2 February)
https://practice.geeksforgeeks.org/problems/find-position-of-set-bit3706/1#
Solution:
if(n==0){
return -1;
}
else{
int a=0;
int index=0;
int c=0;
int count=0;
while(n!=0){
a=n%2;
if(a==1){
c=index;
++count;
if(count>1){
c=-1;
break;
}
}
index++;
n=n/2;
}
if(c==-1){
return -1;
}
else{
return ++c;
}
}
Time:O(log n)[GFG Time: 0.1/2.0]
Space:O(1)
Auxillary Space:O(1)[No recursion stack is used.]
Total Test Cases:102
Approach:
Here we will follow up the digit-wise approach and check for every digit starting from the last of the number.
If the digit is 1 then we will store that index in one variable c and simultaneously we will keep track of the counter variable.
If count >1 then it means more than 2 set bits are there, hence c will be -1 and we will come out of the loop, returning -1 as the final answer.
If count ==1 only then we will return c+1 as we are calculating index from 0 while in question it is demanded from 1.
-----------------------------------------------------------------------------------------------------------------------------
Solution 2:
static int findPosition(int n) {
String s=Integer.toBinaryString(n);
StringBuilder sb=new StringBuilder();
sb.append(s);
sb.reverse();
s=sb.toString();
int start=s.indexOf('1');
int last=s.lastIndexOf('1');
//System.out.println(start);
if(start==last && start!=-1){
return start+1;
}
else{
return -1;
}
}
Time:O(n)[GFG Time: 0.1/2.0 because of previous submission. However, it will take some more time than 0.1 as it follows O(n) order which is greater than O(logn).]
Space:O(1)
Auxillary Space:O(1)[No recursion stack is used.]
Total Test Cases:102
Approach:
Here we follow the approach of comparing the first index and last index of 1.
If both the first index and last index match then it means the position of the set bit is the same and since they will have the same value of index it means there is one particular value of the index for a set bit.
But there is one case when the input number is 0 where start =-1 and last =-1 as in the binary representation of 0 no of ones are 0. So for that case, we need to check whether the number contains a set bit or not. (which I have applied as conditions in code written above.)
Along with that if you traverse in the actual string you will get wrong values for start and end.
Example if number is 2 then binary is 10
start=0
end=0
later in code, you will return 1 while the answer should be 2.
This is so because we are traversing string from MSB to LSB while in question they have mentioned index from LSB to msb traversal.
So first we need to reverse the string and then start traversing.
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment