bharath - 6 months ago 38
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