user2660964
user2660964

Reputation: 141

Inverted Multiplication Pyramid

I have an inverted pyramid. At the top there are numbers from 1 to N. Below, we write out (N – 1) numbers, each of which is the product of two numbers that are above it. And so forth for each row.

For example (n = 4):

1       2       3       4
    2       6      12
       12      72
          864

I have to find the first digit of the final number. Can this be done in O(N)? Maybe there is a specific algorithm?

Upvotes: 2

Views: 137

Answers (1)

AbcAeffchen
AbcAeffchen

Reputation: 14987

First lets have a look at the factors

1¹         2¹         3¹         4¹
    1¹⋅2¹      2¹⋅3¹      3¹⋅4¹
       1¹⋅2²⋅3¹    2¹⋅3²⋅4¹
            1¹⋅2³⋅3³⋅4¹

If you look at the exponents you see pascals triangle.

So the formular for the last element of your multiplication pyramid is

pn = Πk=1,...,n nbinom(n-1,k-1)

Now you "only" have to get the first digit dn of the result. You could do this by calculating

dn = floor( pn / 10floor( log10(pn) ) )
   = floor( 10log10(pn) / 10floor( log10(pn) ) )
   = floor( 10log10(pn) - floor( log10(pn) ) )

To avoid the giant numbers, you can calculate log(pn) directly by

log(pn) = Σk=1,...,n binom(n-1,k-1)⋅log(k)

Example:

d₄ = floor( 10log₁₀(864) - floor( log₁₀(864) ) ) 
   = floor( 102.936513742 - 2 )
   = floor( 100.936513742)
   = floor( 8.64 )
   = 8

To calculate log(pn), you have to do n multiplications and n-1 additions. After this you have to calculate only a constant number of operations, so this would be run in O(n).

Upvotes: 2

Related Questions