Print the values ​​(3 ^ i * 7 ^ j) in ascending and optimal order

Question

I came across interview questions in which you are asked to print the value 3 i * 7 j in ascending order, but in an optimal way. eg,

3 0 * 7 0 = 1
3 1 * 7 0 = 3
3 0 * 7 1 = 7
3 2 * 7 0 = 9
3 1 * 7 1 = 21
3 3 * 7 0 = 27

etc.

Answer 1

You can use heap . Start by inserting the smallest value ( 3^0 * 7^0 ). At each step, type a minimum (this will be the root of your heap), delete it and add 3 * minimum and 7 * minimum to the heap.

This has a time complexity of O(log n) .

Answer 2

 A(i,j)=3^i * 7^j when i != 0 and j != 0: A(i,j)=A(i-1,j-1)*21 when i!=0 and j==0: A(i,0)=A(i-1,0)*3 when i==0 and j!=0: A(0,j)=A(0,j-1)*7 when i==0 and j==0: A(0,0)=1 

You can store them in a two-dimensional array so that you can get the same value from it.

Answer 3

The only thing I can think of when you say that the optimal one is to calculate it and save the values ​​in the table. then calculate only the multiplication

  long[] threePower = new long[10]; long[] sevenPower = new long[10]; threePower[0] = sevenPower[0] = 1; for (int i = 1; i < 10; i++) { threePower[i] = threePower[i - 1]*3; sevenPower[i] = sevenPower[i - 1] * 7; } 

and then print the combinations