Given three non-negative integers x, y and bound, the task is to print all the powerful integer ? bound in sorted order.
A powerful integer is of the form xi + yj for all i, j ? 0.
Examples:
Input: x = 3, y = 5, bound = 10
Output: 2 4 6 8 10
30 + 50 = 1 + 1 = 2
30 + 51 = 1 + 5 = 6
31 + 50 = 3 + 1 = 4
31 + 51 = 3 + 5 = 8
32 + 50 = 9 + 1 = 10Input: x = 2, y = 3, bound = 10
Output: 2 3 4 5 7 9 10
Approach: Initialize i = 0 for outer loop and j = 0 for inner loop, if xi = bound then break out of the outer loop (as adding any power of y to it will make it out of the bound). If xi + yj > bound then break out of the inner loop and in every other iteration of the inner loop, save xi + yj in a set to maintain a distinct and sorted list of the powerful integers. Print the contents of the set in the end.
To avoid calculating the powers of y again and again, all the powers of y can be pre-calculated and stored in a vector.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to print powerful integers void powerfulIntegers(int x, int y, int bound) { // Set is used to store distinct numbers // in sorted order set<int> s; vector<int> powersOfY; int i; // Store all the powers of y < bound in a vector // to avoid calculating them again and again powersOfY.push_back(1); for (i = y; i < bound && y!= 1; i = i * y) powersOfY.push_back(i); i = 0; while (true) { // x^i int xPowI = pow(x, i); for (auto j = powersOfY.begin(); j != powersOfY.end(); ++j) { int num = xPowI + *j; // If num is within limits // insert it into the set if (num <= bound) s.insert(num); // Break out of the inner loop else break; } // Adding any number to it // will be out of bounds if (xPowI >= bound || x == 1) break; // Increment i i++; } // Print the contents of the set set<int>::iterator itr; for (itr = s.begin(); itr != s.end(); itr++) { cout << *itr << " "; } } // Driver code int main() { int x = 2, y = 3, bound = 10; // Print powerful integers powerfulIntegers(x, y, bound); return 0; } |
Java
// Java implementation of the approach import java.util.*; import java.lang.Math; class GfG { // Function to print powerful integers static void powerfulIntegers(int x, int y, int bound) { // Set is used to store distinct numbers // in sorted order Set<Integer> s = new HashSet<>(); ArrayList<Integer> powersOfY = new ArrayList<>(); int i; // Store all the powers of y < bound in a vector // to avoid calculating them again and again powersOfY.add(1); for (i = y; i < bound && y != 1; i = i * y) powersOfY.add(i); i = 0; while (true) { // x^i int xPowI = (int)Math.pow((double)x, (double)i); for (int j = 0; j < powersOfY.size(); ++j) { int num = xPowI + powersOfY.get(j); // If num is within limits // insert it into the set if (num <= bound) s.add(num); // Break out of the inner loop else break; } // Adding any number to it // will be out of bounds if (xPowI >= bound || x == 1) break; // Increment i i++; } // Print the contents of the set Iterator itr = s.iterator(); while(itr.hasNext()) { System.out.print(itr.next() + " "); } } // Driver code public static void main(String []args) { int x = 2, y = 1, bound = 10; // Print powerful integers powerfulIntegers(x, y, bound); } } |
Python3
# Python3 implementation of the approach # Function to print powerful integers def powerfulIntegers(x, y, bound) : # Set is used to store distinct # numbers in sorted order s = set() powersOfY = [] # Store all the powers of y < bound # in a vector to avoid calculating # them again and again powersOfY.append(1) i = y while i < bound and y!=1 : powersOfY.append(i) i *= y i = 0 while (True) : # x^i xPowI = pow(x, i) for j in powersOfY : num = xPowI + j # If num is within limits # insert it into the set if (num <= bound) : s.add(num) # Break out of the inner loop else : break # Adding any number to it # will be out of bounds if (xPowI >= bound or x == 1) : break # Increment i i += 1 # Print the contents of the set for itr in s : print(itr, end = " ")# Driver code if __name__ == "__main__" : x = 2 y = 3 bound = 10 # Print powerful integers powerfulIntegers(x, y, bound)# This code is contributed by Ryuga |
C#
// C# implementation of the approach using System; using System.Linq; using System.Collections.Generic; using System.Collections; class GFG { // Function to print powerful integers static void powerfulIntegers(int x, int y, int bound) { // Set is used to store distinct numbers // in sorted order HashSet<int> s = new HashSet<int>(); ArrayList powersOfY = new ArrayList(); int i; // Store all the powers of y < bound in a vector // to avoid calculating them again and again powersOfY.Add(1); for (i = y; i < bound && y != 1; i = i * y) powersOfY.Add(i); i = 0; while (true) { // x^i int xPowI = (int)Math.Pow(x, i); for (int j = 0; j != powersOfY.Count; ++j) { int num = xPowI + (int)powersOfY[j]; // If num is within limits // insert it into the set if (num <= bound) s.Add(num); // Break out of the inner loop else break; } // Adding any number to it // will be out of bounds if (xPowI >= bound || x == 1) break; // Increment i i++; } int[] ar = s.ToArray(); Array.Sort(ar); s.Clear(); s.UnionWith(ar); // Print the contents of the set foreach (int t in s) { Console.Write( t + " "); } } // Driver code static void Main() { int x = 2, y = 3, bound = 10; // Print powerful integers powerfulIntegers(x, y, bound); } } // This code is contributed by mits |
PHP
<?php // PHP implementation of the approach // Function to print powerful integers function powerfulIntegers($x, $y, $bound) { // Set is used to store distinct // numbers in sorted order $s = array(); $powersOfY = array(); // Store all the powers of y < bound // in a vector to avoid calculating // them again and again array_push($powersOfY, 1); $i = $y; while($i < $bound && $y != 1) { array_push($powersOfY, $i); $i *= $y; } $i = 0; while (true) { // x^i $xPowI = pow($x, $i); for ($j = 0; $j < count($powersOfY); $j++) { $num = $xPowI + $powersOfY[$j]; // If num is within limits // insert it into the set if ($num <= $bound) array_push($s, $num); // Break out of the inner loop else break; } // Adding any number to it // will be out of bounds if ($xPowI >= $bound || $x == 1) break; // Increment i $i += 1; } $s = array_unique($s); sort($s); // Print the contents of the set foreach ($s as &$itr) print($itr . " "); } // Driver code $x = 2; $y = 3; $bound = 10; // Print powerful integers powerfulIntegers($x, $y, $bound); // This code is contributed by chandan_jnu ?> |
Javascript
<script>// Javascript implementation of the approach // Function to print powerful integers function powerfulIntegers(x, y, bound) { // Set is used to store distinct numbers // in sorted order var s = new Set(); var powersOfY = []; var i; // Store all the powers of y < bound in a vector // to avoid calculating them again and again powersOfY.push(1); for(i = y; i < bound && y!= 1; i = i * y) powersOfY.push(i); i = 0; while (true) { // x^i var xPowI = Math.pow(x, i); powersOfY.forEach(j => { var num = xPowI + j; // If num is within limits // insert it into the set if (num <= bound) s.add(num); }); // Adding any number to it // will be out of bounds if (xPowI >= bound || x == 1) break; // Increment i i++; } // Print the contents of the set [...s].sort((a, b) => a - b).forEach(itr => { document.write(itr + " ") });} // Driver code var x = 2, y = 3, bound = 10; // Print powerful integers powerfulIntegers(x, y, bound); // This code is contributed by itsok</script> |
Output:
2 3 4 5 7 9 10
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
