algorithm - Given an integer z<=10^100, find the smallest row of Pascal's triangle that contains z -

how can find algorithm solve problem using c++: given integer z<=10^100, find smallest row of pascal's triangle contains number z.

    1    1 1   1 2 1  1 3 3 1 1 4 6 4 1 

for example if z=6 => result on 4th row.

another way describe problem: given integer z<=10^100, find smallest integer n: exist integer k c(k,n) = z.

c(k,n) combination of n things taken k @ time without repetition

edit solution needs logarithmic time, it's o(log z). or maybe o( (log z)^2 ).

say looking n,k binomial(n,k)==z given z.

1. each row has largest value in middle, starting n=0 increase row number, n, long middle value smaller given number. actually, 10^100 isn't big, before row 340 find position n0,k0=n0/2 value triangle larger or equal z: binomial(n0,k0)>=z

2. you walk left, i.e. decrease column number k, until find value smaller z. if there matching value in row have hit now. k not large, less 170, step won't executed more , not present performance problem.

3. from here walk down, increasing n. here find steadily increasing value of binomial[n,k]. continue 3 until value gets bigger or equal z, goto 2.

edit: step 3 can loop long time when row number n large, instead of checking each n linearly can binary search n binomial(n,k) >= z > binomial(n-1,k), needs log(n) time.

a python implementation looks this, c++ similar more cumbersome because need use additional library arbitrary precision integers:

# calculate (n-k+1)* ... *n def getnk( n, k ):     = n     u in range( n-k+1, n ):         = * u     return  # find n such binomial(n,k) >= z , binomial(n-1,k) < z def find_n( z, k, n0 ):     kfactorial = k     u in range(2, k):         kfactorial *= u      xk = z * kfactorial                  nk0 = getnk( n0, k )     n1=n0*2     nk1 = getnk( n1, k )      # duplicate n while value small     while nk1 < xk:         nk0=nk1         n0=n1         n1*=2         nk1 = getnk( n1, k )     # binary search     while n1 > n0 + 1:         n2 = (n0+n1) // 2         nk2 = getnk( n2, k )         if nk2 < xk:             n0 = n2             nk0 = nk2         else:             n1 = n2             nk1 = nk2      return n1, nk1 // kfactorial   def find_pos( z ):     n=0     k=0     nk=1      # start finding row middle value bigger z     while nk < z:         # increase n         n = n + 1         nk = nk * n // (n-k)         if nk >= z:             break         # increase both n , k         n = n + 1         k = k + 1         nk = nk * n // k      # check subsequent rows matching value     while nk != z:         if nk > z:             # decrease k             k = k - 1             nk = nk * (k+1) // (n-k)         else:             # increase n             # either linearly             #  n = n + 1             #  nk = nk * n // (n-k)             # or using binary search:             n, nk = find_n( z, k, n )     return n, k  z = 56476362530291763837811509925185051642180136064700011445902684545741089307844616509330834616 print( find_pos(z) ) 

it should print

(5864079763474581, 6)