Leetcode 397 Solution

This article provides solution to leetcode question 397 (integer-replacement)
Categories:
Tags:
Access this page by simply typing in "lcs 397" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/integer-replacement

Solution

class Solution {
public:
    int integerReplacement(int n) {
        queue<int64_t> q;
        set<int64_t> s;



        q.push(n);
        s.insert(n);



        int step = 0;



        while (q.empty() == false)
        {
            int size = q.size();



            for (int i = 0; i < size; i++)
            {
                int64_t curr = q.front();
                q.pop();



                if (curr == 1)
                    return step;



                if (curr % 2 == 0)
                {
                    if (s.find(curr / 2) == s.end())
                        q.push(curr / 2), s.insert(curr / 2);
                }
                else
                {
                    if (s.find(curr - 1) == s.end())
                        q.push(curr - 1), s.insert(curr - 1);



                    if (s.find(curr + 1) == s.end())
                        q.push(curr + 1), s.insert(curr + 1);
                }
            }



            step++;
        }



        return -1;
    }
};