CODEWITHSUNDEEP
pythonpython-3.x
snake_case_typing
snake_case_typing

Reputation: 161

Number of solutions in a certain range such that the sum of two (smaller) numbers is greater than the third (largest)

I have to find number of solutions in a certain range(x,y) that satisfy the triangle inequality
x and y are only integers and (0 <x <y <10,000)

For an example interval (2, 5) The correct answer is 3
Explanation of the example:
there are 4 combinations:
2 3 4
2 3 5
2 4 5
3 4 5
The triangle inequality is true for all combinations except one (2,3,5), so the correct answer is 3.

I just found a way to calculate all the combinations from the Newton symbol (code below)
But I don't know how to find only those values ​​that satisfy the triangle inequality

from math import factorial
### n = (y-x)+1
### n! / ((n-k)! * k!)  
# math.factorial(x) = x!

x = int(input("Enter x: "))
y = int(input("Enter y: "))

if(y-x+1 < 3 ):
      result = 0
else:      
   k = 3
   n = y-x+1

   number_of_combinations = int(factorial(n) / (factorial(n-k)*factorial(k)))
   print(f"Number of combinations:{number_of_combinations}")

Thank you in advance for your help

Upvotes: 0

Views: 46

Answers (2)

Riccardo Bucco
Riccardo Bucco

Reputation: 15384

Try this:

interval = [
    int(input('Enter first endpoint: ')),
    int(input('Enter second endpoint: ')),
]

for z in range(interval[0] + 2, interval[1] + 1):
    for y in range(interval[0] + 1, z):
        for x in range(z - y + 1, y):
            print(x, y, z)

Upvotes: 0

user7864386
user7864386

Reputation:

You can use itertools.combinations to create all 3-combinations and simply iterate over them count.

From the docs:

The combination tuples are emitted in lexicographic ordering according to the order of the input iterable. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

So if you have an interval, that means it's sorted, so you can just compare the first two to the third element in each tuple.

from itertools import combinations
lst = list(range(2,6))
count = 0
for x,y,z in combinations(lst, 3):
    count += x+y > z

Same code as a one-liner:

count = sum(x+y > z for x,y,z in combinations(lst, 3))

Output:

3

If you need the tuples that satisfy it, then:

out = [(x,y,z) for x,y,z in combinations(lst, 3) if x+y > z]

Output:

[(2, 3, 4), (2, 4, 5), (3, 4, 5)]

Upvotes: 1

Related Questions