Lucky alive person in a circle | Set | package whatever do not write package name here ; Here is a O ( 1 ) solution for this problemit will work for 32 bit integers ] ; Suppose n is 273 ( binary is 100010001 ) . It does following 100010001 | 010001000 = 110011001 ; This makes sure 4 bits ( From MSB and including MSB ) are set . It does following 110011001 | 001100110 = 111111111 ; Increment n by 1 so that there is only one set bit which is just before original MSB . n now becomes 1000000000 ; Return original MSB after shifting . n now becomes 100000000 ; to calculate the highest number which is power of 2 and less than n ; return the correct answer as per the approach in above article ; Driver Code
import java . io . * ; class GFG { static int setBitNumber ( int n ) { n |= n >> 1 ; n |= n >> 2 ; n |= n >> 4 ; n |= n >> 8 ; n |= n >> 16 ; n = n + 1 ; return ( n >> 1 ) ; } static int luckiest_person ( int n ) { int nearestPower = setBitNumber ( n ) ; return 2 * ( n - nearestPower ) + 1 ; } public static void main ( String [ ] args ) { int N = 8 ; int lucky_p = luckiest_person ( N ) ; System . out . print ( lucky_p ) ; } }