DukeXar
BAN USER#include <iostream>
#include <iomanip>
#include <vector>
void print(std::vector<bool> const & number)
{
for (int i = number.size(); i > 0; --i) {
std::cout << (int)number[i-1];
}
std::cout << std::endl;
}
void modify(std::vector<bool> & number, std::vector<int> & base, std::vector<int> const & cnt)
{
for (int i = 0; i < number.size(); ++i) {
--base[i];
if (base[i] == 0) {
number[i] = number[i] ^ 1;
base[i] = cnt[i];
}
}
}
void solve(int n)
{
std::vector<bool> number(n, false);
// idx: 3 2 1 0
// cnt: 16 8 4 2
// base: 8 4 2 1
std::vector<int> base(n, 0);
std::vector<int> cnt(n, 0);
for (int i = 0; i < base.size(); ++i) {
base[i] = 1 << i;
cnt[i] = 1 << (i+1);
}
long long total = (long long)1 << n;
// the loop condition can be changed so it breaks out when 0000...0000 appears after 'modify' call, in that case the "n" can be very large
// now it is limited to number of bits in long long - 1
for (long long idx = 0; idx < total; ++idx) {
std::cout << std::setw(3) << idx << ' ';
print(number);
modify(number, base, cnt);
}
}
int main()
{
int n;
std::cin >> n;
solve(n);
return 0;
Use modified version of Kadane algorithm to find max subarray sum and run it two times: starting from 0 and starting from 1. So the space complexity is constant, runtime O(N). This version also outputs numbers, participated in sum:
- DukeXar June 07, 2013