bharath - 26 days ago 9

Python Question

I'm trying to find the multiple pair of a number with least sum in O(1).

Here is the explanation :

`If number is 100. Then all the possible pairs are :`

1 X 100

2 X 50

4 X 25

5 X 20

10 X 10

20 X 5

25 X 4

50 X 2

100 X 1

Here the pair with least sum is 10,10 which is clearly the middle one

`Similarly if number is 12 then pairs are as follows`

1 X 12

2 X 6

3 X 4

4 X 3

6 X 2

12 X 1

Here the required pair is either 3,4 or 4,3.

`If a number has 'p' pairs then the required one is always ceil(p/2).`

If the given number is a perfect square then the task is pretty simple.The pair would be just

`sqrt(number),sqrt(number).`

If not then the pair would be either

`ceil(sqrt(number)),number/ceil(sqrt(number))`

**given that ceil(sqrt(number)) is a multiple of number**

`immediate multiple neighbour of sqrt(number):`

For example consider '6'. 6 is not a perfect square.

ceil of sqrt(6) is 3 and 3 is a multiple of 6.So the required pair is

`3,6/3=2`

`Now consider 102. All pairs are :`

1 * 102.0

2 * 51.0

3 * 34.0

6 * 17.0

17 * 6.0

34 * 3.0

51 * 2.0

102 * 1

The required pair in this is 17,6 or 6,17.

`Here ceil(sqrt(102)) is 11`

**Now this is what we actually find.**

Here is my O(n) implementation :

`import math`

l = []

n = int(input())

for i in range(1, n + 1):

if n % i is 0:

l.append(i)

middle = l[math.ceil(len(l) / 2)]

print("Required pair is ", middle, ",", n / middle)

Answer Source

Here is the proof that finding the pair must at least be as hard as integer factoring (which implies there is no known O(1) algorithm):

If we start with a number N and get the pair with the smallest sum, as it was shown, the divisors are the closest to the sqrt(N) so there only 2 possibilities:

1. The pair is 1 - N which means N is a prime. Which is the trivial case.

2. We found some non-trivial divisor k. Which means we can apply the algorithm successively for k and N/k, eventually finding all the prime divisors efficiently.