algorithm
mathematics
problem-solving
coding
pair-comparison

How to find pairs with product greater than sum

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Finding pairs of numbers where the product is greater than the sum can be an intriguing computational problem that involves both elementary algebra and coding ability. Such pairs are significant in certain problem-solving scenarios, algorithm optimization tasks, and even competitive programming. In this article, we'll explore the conditions under which two numbers yield a product greater than their sum, provide a mathematical rationale, and demonstrate how to implement this in code.

Understanding the Problem

Given two numbers, `a` and `b`, we want to determine when:

a×b>a+ba \times b > a + b

Rearranging this inequality gives:

a×bab>0a \times b - a - b > 0

Adding 1 to both sides yields:

a×bab+1>1a \times b - a - b + 1 > 1

This expression can be factored as:

(a1)(b1)>1(a - 1)(b - 1) > 1

This final inequality gives us a clear condition: the product of `(a-1)` and `(b-1)` must be greater than 1.

Mathematical Evaluation

Analyzing the derived inequality `(a-1)(b-1) > 1`, consider both `a` and `b`:

  • Case 1: Both `a` and `b` are greater than 2:
    If `a > 2` and `b > 2`, then `(a-1) > 1` and `(b-1) > 1`. Thus, the product `(a-1)(b-1)` is naturally greater than 1.
  • Case 2: One of the numbers is 2 or less:
    If one of the numbers is less or equal to 2, the inequality may or may not hold. Special attention should be given when `a` or `b` equals 1, as their corresponding product with the other number frequently fails the inequality, unless both numbers are 1, in which case the inequality holds because: `(1-1)(1-1) = 0 > 1` is false, but for larger numbers, calculations must be explicitly checked.
  • Case 3: Both numbers are negative:
    Negative numbers introduce another complexity. However, negative-numbers scenarios usually result in a negative result for `(a-1)(b-1)`, which won't satisfy the inequality.

Example Cases

  1. Example 1: `a = 3, b = 4`
    (a1)(b1)=2×3=6>1(a-1)(b-1) = 2 \times 3 = 6 > 1
    Here, the condition holds.
  2. Example 2: `a = 2, b = 5`
    (a1)(b1)=1×4=4>1(a-1)(b-1) = 1 \times 4 = 4 > 1
    Here, the condition holds.
  3. Example 3: `a = -2, b = -3`
    (a1)(b1)=(3)(4)=12(a-1)(b-1) = (-3)(-4) = 12, which is positive, yet we revisit as inputs due to context validity in the negative range.

Algorithm Implementation

Let's write a Python function that takes a list of numbers and returns all pairs that meet our product > sum condition.


Course illustration
Course illustration

All Rights Reserved.