bharath bharath - 26 days ago 9
Python Question

Getting multiples of a number with least sum in O(1)

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


or the
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
. The immediate multiple neighbour of 11 is 17 or 6.
Now this is what we actually find.


How do we find that immediate multiple neighbour ?

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)


EDIT: StefanPochmann I've corrected that typing mistake. Hope this would answer your question

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.