Print the values of (3^i *7^j) in increasing order and in optimal way

Question

I encountered an interview questions which asks you to print the value of 3ⁱ * 7^j in increasing order but in optimal way.e.g.

3⁰ * 7⁰ = 1
3¹ * 7⁰ = 3
3⁰ * 7¹ = 7
3² * 7⁰ = 9
3¹ * 7¹ = 21
3³ * 7⁰ = 27

and so on ...

(Yes, the prime factors are different. BFD.) – David Eisenstat Aug 25 '13 at 12:00 — David Eisenstat, Aug 25 '13 at 12:00
JavaScript attempt: http://jsfiddle.net/groovy/TYUBR/ – גלעד ברקן Aug 26 '13 at 05:02 — גלעד ברקן, Aug 26 '13 at 05:02

score 3 · Answer 1 · answered Aug 25 '13 at 10:36

3

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

This has O(log n) time complexity.

answered Aug 25 '13 at 10:36

IVlad

43,099
13
111
179

But "at each step" makes O(n)? – huseyin tugrul buyukisik Aug 25 '13 at 10:39
@huseyintugrulbuyukisik - it is `O(log n)` to find what the next value you should print is, where `n` is however many values you want to print. – IVlad Aug 25 '13 at 10:41

score 0 · Answer 2 · answered Aug 25 '13 at 10:37

0

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 the them into a 2-D array, such that you can get the former value from it.

answered Aug 25 '13 at 10:37

MarshalSHI

615
1
8
17

You are missing the major point , you should print it in increasing order , how it is helpful there? – user2161522 Aug 25 '13 at 17:08

score 0 · Answer 3 · answered Aug 25 '13 at 10:39

0

the only thing i can think of when you say optimal is to calculate it and save in a table the values. 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

answered Aug 25 '13 at 10:39

No Idea For Name

11,411
10
42
70

How will you efficiently print them in increasing order? – IVlad Aug 25 '13 at 10:46
@IVlad in a double for statement – No Idea For Name Aug 25 '13 at 10:48
That would be `O(n^2)` - not very efficient. – IVlad Aug 25 '13 at 11:31
@IVlad you are saying this is O(n^2), what is the n here? the amount of multiplication?, because you are doing the same i believe... when you are saying something on efficiency you have to explain in what are you measuring it – No Idea For Name Aug 25 '13 at 11:49
`n` is the amount of values you are asked to print. The problem doesn't even state that this is given, and your algorithm assumes that it is. Even if you generate enough values, you still haven't explained anything past "print the combinations" - you have to print them in sorted order. Do you just sort them? That's `O(n^2 log n)`. – IVlad Aug 25 '13 at 12:24

Print the values of (3^i *7^j) in increasing order and in optimal way

3 Answers3