Multiset $S$ such that $\{\sum_{x \in S'} x | S' \subseteq S\} = \{0, 1, \ldots, N\}$ and $|S| = O(\log N)$ (tools/logn_integer_partition.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2022-10-15 20:30:06+09:00
Include: #include "tools/logn_integer_partition.hpp"

template <typename T>
std::vector<T> logn_integer_partition(T n);

It returns a multiset $S$ such that $\{\sum_{x \in S’} x | S’ \subseteq S\} = \{0, 1, \ldots, N\}$ and $|S| = O(\log N)$.

Constraints

$n \geq 0$

Time Complexity

$O(\log n)$

License

Author

anqooqie

Verified with

tests/logn_integer_partition.test.cpp

Code

#ifndef TOOLS_LOGN_INTEGER_PARTITION_HPP
#define TOOLS_LOGN_INTEGER_PARTITION_HPP

#include <vector>
#include <cassert>

namespace tools {
  template <typename T>
  ::std::vector<T> logn_integer_partition(T n) {
    assert(n >= 0);
    ::std::vector<T> res;
    for (T pow2 = 1; pow2 < n; n -= pow2, pow2 *= 2) {
      res.push_back(pow2);
    }
    if (n > 0) res.push_back(n);
    return res;
  }
}

#endif

#line 1 "tools/logn_integer_partition.hpp"



#include <vector>
#include <cassert>

namespace tools {
  template <typename T>
  ::std::vector<T> logn_integer_partition(T n) {
    assert(n >= 0);
    ::std::vector<T> res;
    for (T pow2 = 1; pow2 < n; n -= pow2, pow2 *= 2) {
      res.push_back(pow2);
    }
    if (n > 0) res.push_back(n);
    return res;
  }
}