CODEWITHSUNDEEP
pythonalgorithm
arpa
arpa

Reputation: 328

Sum of 2 elements from 2 ranges that will be one given number


I need to make a quick algorithm(I already made a slow one) which will find the number of all possible values from two ranges of integer numbers (ranges can intersect or not) which sum will be the given number

I can represent it like an equation: z = x + y
where z is a known number and equals x plus y
z can be any number between 0 and 10^18

x belongs to a range of integer numbers [a..b], where 0 <= a <= b <= 10^18 and
the difference between the consecutive numbers is 1

y belongs to a range of integer numbers [c..d], where 0 <= c <= d <= 10^18 and
the difference between the consecutive numbers is 1

so I need to find the number(not their exact values) of all the possible variations of x and y from two sets of numbers which sum will be z

Example:
z = 5
first set: a = 1, b = 5(it means the set consists of 1,2,3,4,5)
second set: c = 1, b = 5
then the answer is 4, because all possible combinations are:
x = 4, y = 1
x = 3, y = 2
x = 2, y = 3
x = 1, y = 4
because theirs sums are 5's

The compulsory condition for an algrorithm is to work faster than 1 second

The following code works fine but only with numbers lesser than 1000000. It starts to work much slower with big numbers

with open(r"input.txt") as f:
    n = int(f.readline()) # the given number
    a = int(f.readline()) # the start position of the first set
    b = int(f.readline()) # the end position of the first set
    c = int(f.readline()) # the start position of the second set
    d = int(f.readline()) # the end position of the second set
   # print "n:",n,"a:",a,"b:",b,"c:",c,"d:",d

t = b - a + 1 # all posible variants of the first set
k = d - c + 1 # all posible variants of the second set
number_of_vars = 0 

if t >= k:
    while b >= a:
        if (n - b <= d) \
                and (n - b>= c):
            number_of_vars += 1
            b -= 1
        else:
            b -= 1

if t < k:
    while d >= c:
        if (n-d <= b) and (n-d >= a):
            number_of_vars += 1
            d -= 1
        else:
            d -= 1

print number_of_vars

Upvotes: 0

Views: 148

Answers (2)

John Coleman
John Coleman

Reputation: 51998

No algorithm required -- just algebra:

It suffices to count the number of x in [a,b] for which z - x is in [c,d]

You need both a <= x <= b and c <= z - x <= d. The second inequality is equivalent to z - d <= x <= z - c hence you need

max(a, z - d) <= x <= min(b,z - c)

The number of such x is 0 if min(b,z - c) < max(a, z - d) otherwise it is

min(b,z - c) - max(a, z - d) + 1

In either case the number of solutions is

max(0, min(b,z - c) - max(a, z - d) + 1)

In your example a = c = 1 and b = d = z = 5 and

min(b, z - c) - max(a, z - d) + 1 = min(5,4) - max(1,0) + 1 = 4 - 1 + 1 = 4

Upvotes: 2

Haris
Haris

Reputation: 12270

One thing that you can use to reduce the checks in your algorithm is,

If the range for the 2 sets are overlapping, then you can cancel out some checks. Like in your example,

range for 1st set is 1 to 5

range for 2nd set is 1 to 5

So, if

x = 4, y = 1

is working, then

x = 1, y = 4

will also work. So you have to go only till half the number (i.e till 3 only in this case)

If only a part of the range is overlapping, then you can use the above method for that part, and the remaining part can be checked using normal method.

Upvotes: 1

Related Questions