Could you anyone offer an elegant solution to deal with 2147483647?


  • 6
    D
    public int integerReplacement(int n) {
            if (n == 1) return 0;
            if (n == 2147483647) {
                return Math.min(1 + integerReplacement(2147483647 - 1), 2 + integerReplacement((2147483646 / 2) + 1));
            }
            if (n % 2 == 0) {
                return (1 + integerReplacement(n / 2));
            } else {
                return (1 + Math.min(integerReplacement(n - 1), integerReplacement(n + 1)));
            }
        }
    

  • 0
    V

    You could solve it with Math.abs(integerReplacement(n + 1))


  • 6
    W

    Divide first then add. Check out the updated code below:

    public int integerReplacement(int n) {
        if (n == 1) return 0;
        if (n % 2 == 0) 
            return (1 + integerReplacement(n / 2));
        else 
            return (2 + Math.min(integerReplacement(n/2), integerReplacement(n/2 + 1)));
    }
    

  • 0
    S
    This post is deleted!

  • 1
    H

    For C++, I use int64_t to get rid of the boundary problem, without loosing much efficiency.

    class Solution {
    public:
        int integerReplacement(int n) {
            int64_t nn = n;
            int step = 0;
            while (nn > 1LL) {
                while (nn % 2LL == 0LL) {
                    nn >>= 1LL;
                    ++step;
                }
                if (nn == 1LL)
                    return step;
                    
                if (nn > 3LL && (nn & 2LL)) {
                    ++nn;
                } else {
                    --nn;
                }
                ++step;
            }
            return step;
        }
    };
    

  • 0
    G
        public int integerReplacement(int n) {
            int cnt = 0;
            while (n > 1) {
                if (n % 2 == 0) {
                    n >>>= 1;
                } else if (n <= 3 || (n & 2) == 0){
                    n -= 1;
                }else if (n == Integer.MAX_VALUE) {
                    n = 1 << 30;
                    cnt++;
                } else {
                    n += 1;
                }
                cnt++;
            }
            return cnt;
        }
    

  • 0
    S

    Can someone explain why the INT_MAX would return 33 instead of 32 if the hard coded if statement was removed?


  • 0
    X
    This post is deleted!

  • 1
    C

    There are some points to pay attention to deal with INT_MAX

    • Notice that /2 will keep the signed bit(MSB)
    • For C++, it is implementation dependent to keep MSB or not for shift right
    • So just convert int to unsigned and use shift right by 1 instead of /2

    C++ code below

    class Solution {
    public:
        int integerReplacement(int in) {
            int ret = 0;
            unsigned n = in;
            while (n != 1) {
                if ((n&1) == 0) {
                    n >>= 1;
                } else {
                    if ((n&2) == 0 || n == 3) {
                        n -= 1;
                    } else {
                        n += 1;
                    }
                }
                ret += 1;
            }
            return ret;
        }
    };
    

  • 0
    M

    Convert the input to a 64-bit integer first.


  • 0
    B

    @Davidhunter you can use if(n == Integer.MAX_VALUE) return 32;
    Because it is the only case like what you did for n = 1;


Log in to reply
 

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