Algocademy Logo

Print Powers in JavaScript with Time Complexity O(logAB)


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

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

Output

Constraints

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

Potential pitfalls include handling the case when A is 0 or 1, as these have unique properties (0n is always 0 for n > 0, and 1n is always 1).

Approach

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

  1. Start with the initial power of A, which is 1 (i.e., A0).
  2. Use a loop to repeatedly multiply the current power by A until the power exceeds B.
  3. Print each power during the iteration.

Naive Solution

A naive solution would involve calculating each power of A up to a large number and checking if it is less than or equal to B. This is not optimal as it involves unnecessary calculations.

Optimized Solution

The optimized solution involves using a loop to multiply the current power by A and checking if it is less than or equal to B. This ensures we only compute the necessary powers.

Algorithm

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

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

Code Implementation

// Function to print all powers of A less than or equal to B
function printPowers(A, B) {
  // Initialize the first power of A
  let power = 1;
  
  // Loop until the power exceeds B
  while (power <= B) {
    // Print the current power
    console.log(power);
    
    // Calculate the next power
    power *= A;
  }
}

// Example usage
printPowers(3, 100); // Output: 1, 3, 9, 27, 81

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:

Testing

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

printPowers(3, 100); // Output: 1, 3, 9, 27, 81
printPowers(2, 50);  // Output: 1, 2, 4, 8, 16, 32
printPowers(5, 1);   // Output: 1
printPowers(0, 10);  // Output: 1
printPowers(1, 10);  // Output: 1

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

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 in programming.

Additional Resources

For further reading and practice, consider the following resources: