class Solution {

public:

int integerReplacement(int n) {

int cnt=0;

if(n==INT_MAX)

return 32;

while(n!=1)

{

if(n%2==0)

{

n>>=1;

cnt++;

}

else

{

int x=(n+1)/2,y=(n-1)/2;

if(y%2==0||n==3)

n=n-1;

else

n=n+1;

cnt++;

}

}

return cnt;

}

};