Print all integers that are sum of powers of two given numbers in C++

In this problem, we are given two numbers a and b and an integer bound and we have to print all values less than binding which is the sum of squares of a and b.

Bound >= ai + bj

Let’s take an example to understand the problem −

Input: a=2, b=3, bound=8 Output: 2 3 4 5 7

To solve this problem, we will use nested loops using two variables i and j from 0. The outer loop will have ending condition xi = bound and the inner loop will have ending condition xi + yj > bound. For each iteration of the inner loop, we will store the value of xi + yi in a sorted list contains all such values. And then at the end print all values of the list.

Example

Program to show the implementation of our solution −

 Live Demo

#include <bits/stdc++.h> using namespace std; void powerSum(int x, int y, int bound) {    set<int> sumOfPowers;    vector<int> powY;    int i;    powY.push_back(1);    for (i = y; i < bound; i = i * y)       powY.push_back(i);    i = 0;    while (true) {       int powX = pow(x, i);       if (powX >= bound)          break;       for (auto j = powY.begin(); j != powY.end(); ++j) {          int num = powX + *j;          if (num <= bound)             sumOfPowers.insert(num);          else             break;       }       i++;    }    set<int>::iterator itr;    for (itr = sumOfPowers.begin(); itr != sumOfPowers.end(); itr++) {       cout<<*itr <<" ";    } } int main() {    int x = 2, y = 3, bound = 25;    cout<<"Sum of powers of "<<x<<" and "<<y<<" less than "<<bound<<" are :\n";    powerSum(x, y, bound);    return 0; }

Output

Sum of powers of 2 and 3 less than 25 are − 2 3 4 5 7 9 10 11 13 17 19 25