Start learning free

LESSON 175 OF 409 · LOOPS - CHALLENGES

Print Powers in C++ with Time Complexity Analysis

Practice Read the full explanation

Given two non-negative integers A and B, print to the console all numbers less than or equal to B that are powers of A

Powers of a number are: A0, A1, A2, etc.

An = A multiplied by itself n times

A0 = 1
A1 = A
A2 = A * A
A3 = A * A * A
A4 = A * A * A * A
etc.

Example:

Input: A = 3, B = 100

Output:
1
3
9
27
81

Explanation:
30 = 1
31 = 3
32 = 9
33 = 27
34 = 81
Hints:

We start with the integer 1. We should repeatedly do some instructions (print it then multiply it by A) as long as one condition is satisfied (current power <= B). Sounds familiar?

We should use a variable power, initially equal to 1, in order to store the current power. And we should use a loop (a while loop, or in languages without one a condition-only for loop) to repeatedly check if power <= B and if so, print and update power. How will the code look like?

Set power to 1. While power is less than or equal to B: print power, then multiply power by A.

STEP 1 OF 4
    Ctrl + Enter to check

    C++ · LOOPS - CHALLENGES

    Print Powers in C++, explained

    Problem Definition

    The problem requires us to print all powers of a given number A that are less than or equal to another number B. The powers of A are defined as A0, A1, A2, and so on.

    Input Format

    • Two non-negative integers A and B.

    Output Format

    • All numbers less than or equal to B that are powers of A, printed on separate lines.

    Constraints

    • 0 ≤ A, B ≤ 109

    Assumptions

    • Both A and B are non-negative integers.

    Example

    Input: A = 3, B = 100

Output:
1
3
9
27
81

    Understanding the Problem

    The core challenge is to generate and print all powers of A that do not exceed B. This problem is significant in various applications such as computing exponential growth, analyzing algorithms with exponential time complexity, and more.

    Potential pitfalls include handling large values of A and B and ensuring that the powers do not exceed the limits of typical integer representations.

    Approach

    To solve this problem, we can use a simple iterative approach:

    1. Start with the initial power of A, which is A0 = 1.
    2. Repeatedly multiply the current power by A and check if it is less than or equal to B.
    3. If it is, print the current power and continue; otherwise, stop the iteration.

    Naive Solution

    A naive solution would involve calculating each power of A and checking if it is less than or equal to B. This approach is straightforward but not optimal for very large values of A and B.

    Optimized Solution

    The optimized solution involves using a loop to repeatedly multiply the current power by A and check if it is within the limit B. This approach ensures that we only compute the necessary powers and stop as soon as we exceed B.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Initialize a variable power to 1 (which is A0).
    2. While power is less than or equal to B:
      • Print the current value of power.
      • Multiply power by A to get the next power.

    Code Implementation

    #include <iostream>
using namespace std;

void printPowers(int A, int B) {
    // Initialize the first power of A
    long long power = 1;
    
    // Loop to print all powers of A less than or equal to B
    while (power <= B) {
        cout << power << endl;
        power *= A; // Calculate the next power of A
    }
}

int main() {
    int A, B;
    cout << "Enter A and B: ";
    cin >> A >> B;
    printPowers(A, B);
    return 0;
}

    Complexity Analysis

    The time complexity of this approach is O(logAB) because we are repeatedly multiplying by A until we exceed B. The space complexity is O(1) as we are using a constant amount of extra space.

    Edge Cases

    Potential edge cases include:

    • A = 0: This is a special case since any power of 0 (except 00) is 0. We need to handle this separately.
    • B = 0: The only power of any number that is less than or equal to 0 is 1 (i.e., A0).
    • A = 1: All powers of 1 are 1, so we need to ensure we do not enter an infinite loop.

    Testing

    To test the solution comprehensively, we should include a variety of test cases:

    • Simple cases: A = 2, B = 10
    • Edge cases: A = 0, B = 0; A = 1, B = 100
    • Large values: A = 10, B = 109

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Break down the problem into smaller, manageable parts.
    • Think about the mathematical properties and constraints.
    • Start with a simple solution and then optimize it.
    • Test your solution with various edge cases to ensure robustness.

    Conclusion

    In this blog post, we discussed how to print all powers of a given number A that are less than or equal to another number B. We explored the problem definition, approach, algorithm, and provided a C++ implementation. We also analyzed the complexity and discussed edge cases and testing strategies. Understanding and solving such problems is crucial for developing strong problem-solving skills and algorithmic thinking.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free