Circuit 101

Probability P(x) can be defined as a/b, where a = number of ways x can be made and b = number of all possible outcomes. Now b = product of (ri-li+1) for i = 0 to n-1. Now there are two ways to calculate a,

Way 1(Dynamic Programming):

Let's define a function f(i,x) which represent the number of ways x can be made using resistors from 0 to i (0-based indexing). Then f(i,x) = sum of f(i-1,x-j) where j=li to ri. Now to reduce memory iterative approach can be adopted with row swap technique. To reduce the loop for calculating the sum you can keep cumulative sum of a row in an array and update it after calculating each row.

Way 2(Convolution):

Let's define n polynomials pi(a) = ali + ali+1 .... + ari for i = 0 to n-1. Now multiplying these n polynomials the co-efficient of ax gives the number of ways to make x using n resistors. Now to multiply the polynomials FFT(Fast Fourier Transformation) can be used to reduce the runtime of the solution.