Start learning free

LESSON 176 OF 410 · LOOPS - CHALLENGES

Print Powers in Java with Time Complexity O(logAB)

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

    JAVA · LOOPS - CHALLENGES

    Print Powers in Java, 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 number A are defined as A0, A1, A2, and so on.

    Input:

    • Two non-negative integers A and B.

    Output:

    • All numbers less than or equal to B that are powers of A.

    Constraints:

    • 0 ≤ A, B ≤ 109

    Assumptions:

    • Both A and B are non-negative integers.

    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, and more.

    Potential Pitfalls and Misconceptions:

    • Assuming that A is always greater than 1. If A is 0 or 1, the behavior changes.
    • Not handling large values of A and B efficiently.

    Approach

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

    Naive Solution:

    We can start with the number 1 (which is A0) and keep multiplying it by A until the result exceeds B. This approach is straightforward but efficient for this problem.

    Optimized Solution:

    The naive solution is already optimal for this problem since it directly computes the required powers without unnecessary computations. The time complexity is O(logAB) because the number of multiplications is proportional to the logarithm of B base A.

    Algorithm

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

    1. Initialize a variable power to 1 (which is A0).
    2. Use a while loop to check if power is less than or equal to B.
    3. Inside the loop, print the current value of power.
    4. Multiply power by A to get the next power of A.
    5. Repeat until power exceeds B.

    Code Implementation

    public class PrintPowers {
    public static void main(String[] args) {
        int A = 3; // Base number
        int B = 100; // Upper limit

        // Initialize the first power of A
        long power = 1;

        // Loop to print all powers of A less than or equal to B
        while (power <= B) {
            System.out.println(power); // Print the current power
            power *= A; // Calculate the next power of A
        }
    }
}

    Complexity Analysis

    The time complexity of this approach is O(logAB) because the number of iterations is proportional to the logarithm of B base A. The space complexity is O(1) as we are using a constant amount of extra space.

    Edge Cases

    Consider the following edge cases:

    • A = 0: Only 00 = 1 should be printed.
    • A = 1: Only 10 = 1 should be printed.
    • B = 0: Only 1 should be printed if A is not 0.
    • Large values of A and B: Ensure the solution handles large numbers without overflow.

    Testing

    To test the solution comprehensively, consider the following test cases:

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

    Thinking and Problem-Solving Tips

    When approaching such problems:

    • Break down the problem into smaller, manageable parts.
    • Consider edge cases and how to handle them.
    • Think about the most efficient way to solve the problem.
    • Practice similar problems to improve problem-solving skills.

    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, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills.

    Additional Resources

    For further reading and practice, consider the following resources:

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