Reputation: 141
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
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