Back to General discussions forum
def fact(n): if n==0: return(1) else: return(n*fact(n-1))
def combination(n,r): if n>=r: return int(fact(n)/((fact(n-r))*(fact(r)))) else: return(0)
No=1 while No>0: Numberofdigits,Base=map(int,input().split()) if Numberofdigits%2==0: Numberofdigits=int(Numberofdigits/2) count=1 else: Numberofdigits=int((Numberofdigits-1)/2) count=2 Base=Base-1 Sum=NumberofdigitsBase t=0 if count==1: while Sum>=0: j=0 S=0 while Sum-j>=0: if (Sum-j)%(Base+1)==0: k=((-1)(int((Sum-j)/(Base+1))))(combination(Numberofdigits,int((Sum-j)/(Base+1))))(combination(j+Numberofdigits-1,j)) S=S+k j+=1 t=t+S*S Sum-=1 print(t) print(' ') if count==2: if Number_of_digits>0: while Sum>=0: j=0 S=0 while Sum-j>=0: if (Sum-j)%(Base+1)==0: k=((-1)(int((Sum-j)/(Base+1))))(combination(Numberofdigits,int((Sum-j)/(Base+1))))(combination(j+Numberofdigits-1,j)) S=S+k j+=1 t=t+SS Sum-=1 print(t*(Base+1)) print(' ') else: print(Base+1) print(' ') No-=1
where is my code going wrong
You are losing precision in combination(n, r). For example, try (n, r) = (83, 67) or (89, 73). When replaced with correct values, your code produces correct answers.
can i know how i could prevent from losing precision?( instead of using dynamic programming)
There are definitely more efficient ways to calculate (n, r). One way is described in the "Combinations Counting" problem. Alternatively you can just use a built-in function from external libraries...
thank you so much it worked