Powers of Two in Order
National Olympiad — National round (2017 season)
Submission name: power2.cpp
Problem summary
From a sequence of positive integers, print all elements that are powers of two, in increasing order. Retain repeated occurrences. The number 1 is also a power of two.
Input
n, followed by n positive integers.
Output
The selected numbers separated by single spaces, or No if none qualify.
Constraints
2 ≤ n ≤ 100; each value ≤ 10000000000.
Worked example
An independently prepared example for this explanation.
Input
5 16 17 27 3 4
Output
4 16
Solution analysis
- A positive integer is a power of two exactly when its binary representation has one set bit. Clearing its lowest set bit with x & (x−1) gives zero exactly in that case.
- Collect all qualifying elements and sort the collection. The task selects elements rather than distinct values, so keep duplicates. Use long long because values may exceed 32-bit limits.
- For 16,17,27,3,4, only 16 and 4 have one set bit. Sorting them produces 4 16. For a sequence containing only 3 and 5, the collection is empty and the output is No.
Why it works
A positive number has one set bit if and only if it is 2 raised to a nonnegative integer power. The bit test therefore accepts exactly the required elements, and sorting places all accepted occurrences in increasing order.
Watch out. Include 1 = 2⁰. Do not discard duplicates or use a 32-bit integer for the input.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> powers;
for (int i = 0; i < n; ++i) {
long long value;
cin >> value;
// A positive power of two has exactly one set bit.
if ((value & (value - 1)) == 0) {
powers.push_back(value);
}
}
sort(powers.begin(), powers.end());
if (powers.empty()) {
cout << "No\n";
} else {
for (size_t i = 0; i < powers.size(); ++i) {
if (i > 0) {
cout << ' ';
}
cout << powers[i];
}
cout << '\n';
}
}