5-Line Concise C++ Solution Using Long Long Type


  • 0
    A

    The use of long long is to avoid the special case of INT_MAX. The key thought is, when we meet an odd, we make the "++ or --" choice by seeing which would be an even : (n - 1) / 2 or (n + 1) / 2.

    int integerReplacement(int n) {
            int count = 0;
            for (long long ln = (long long)n; ln > 1; ++ count) {
                if (ln & 1) ln += (ln != 3 && (((ln - 1) >> 1) & 1)) ? 1 : -1;
                else ln = (ln >> 1);
            }
            return count;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.