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;
    }
};