LeetCode/cpp/reordered-power-of-2.cpp

#include <algorithm>
#include <cassert>
#include <vector>

namespace {

bool is_power_of_2(int n) { return (n & (n - 1)) == 0; }

class permutations {
    using values_t = typename std::vector<char>;

    class p_iter {
        values_t elements;
        bool last;

      public:
        p_iter(values_t elements, bool last = false)
            : elements(elements), last(last) {}

        const values_t &operator*() const { return elements; }

        p_iter &operator++() {
            if (!std::next_permutation(elements.begin(), elements.end())) {
                last = true;
            }
            return *this;
        }

        bool operator==(const p_iter &other) const {
            return last == other.last && elements == other.elements;
        }

        bool operator!=(const p_iter &other) const { return !(*this == other); }
    };

    values_t elements;

  public:
    permutations(const values_t &input_ints) : elements(input_ints) {
        std::sort(elements.begin(), elements.end());
    }

    p_iter begin() const { return {elements, elements.empty()}; }
    p_iter end() const { return {elements, true}; }
};

std::vector<char> to_vector(int n) {
    if (n == 0) {
        return std::vector<char>(1, 0);
    }

    std::vector<char> digits;

    while (n > 0) {
        digits.push_back(n % 10);
        n /= 10;
    }

    return digits;
}

int to_number(const std::vector<char> digits) {
    int number = 0;

    for (auto digit : digits) {
        number = number * 10 + digit;
    }

    return number;
}

} // namespace

class Solution {
  public:
    bool reorderedPowerOf2(int n) {
        for (const auto &permutation : permutations(to_vector(n))) {
            if (permutation.front() == 0) {
                continue;
            }

            if (is_power_of_2(to_number(permutation))) {
                return true;
            }
        }

        return false;
    }
};

int main() {
    Solution s;

    assert(s.reorderedPowerOf2(1));
    assert(s.reorderedPowerOf2(2));
    assert(s.reorderedPowerOf2(4));
    assert(s.reorderedPowerOf2(8));
    assert(s.reorderedPowerOf2(16));
    assert(s.reorderedPowerOf2(61));

    assert(!s.reorderedPowerOf2(10));
    assert(!s.reorderedPowerOf2(20));

    return 0;
}