CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Nov 2011
Posts
2

## Lowest distance

Hi.

I've got the problem to solve:

We've got n numbers. The "distance" between two numbers d(A,B) is the amount of prime numbers (got after factorization) of the number A*B/GCD(A,B)^2. We have to output (for every given numbers) the lowest position of number whose distance between the actual number is lowest. Of course the position of actual number can't be the same as the position of number to output (but the values can).

For example:

We've got six numbers:

1,2,3,4,5,6

And the correct output is: 2,1,1,2,1,2.

I've already written the algorithm working in O(n^2) - which compares every numbers, counts the minimal distance and position and output it. But unfortunately that's too slow. I need someting working in O(nlogn). Could somebody help me with this problem?

Thanks and sorry for my bad English.

2. ## Re: Lowest distance

Originally Posted by boost
I've already written the algorithm working in O(n^2) - which compares every numbers, counts the minimal distance and position and output it. But unfortunately that's too slow. I need someting working in O(nlogn). Could somebody help me with this problem?
How do you know an algorithm that is faster than O(n^2) exists?
The way you presented the problem, you should calculate n^2 (seemingly unrelated) distances. How do you intend to do that faster than O(n^2)?

3. Junior Member
Join Date
Nov 2011
Posts
2

## Re: Lowest distance

Simply... it's written that n<=100000, so it will take hours to count it with an algorithm running in O(n^2).

Originally it's said that "distance" between A and B is an amount of operations required to get number A from B. By operation we understand multiplication or factorization by some prime number.

4. ## Re: Lowest distance

Originally Posted by boost
Simply... it's written that n<=100000, so it will take hours to count it with an algorithm running in O(n^2).
I don't understand. How do you go from O(n^2) and n <= 100000 to hours? They are unrelated. Maybe your implementation is just inefficient.
Originally Posted by boost
Originally it's said that "distance" between A and B is an amount of operations required to get number A from B. By operation we understand multiplication or factorization by some prime number.
Perhaps a faster approach can be found by first factorizing each number into primes, then ordering them somehow, such that it becomes easy to find the closest number.

5. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Lowest distance

Originally Posted by boost
I've already written the algorithm working in O(n^2) - which compares every numbers, counts the minimal distance and position and output it. But unfortunately that's too slow. I need someting working in O(nlogn). Could somebody help me with this problem?
So you fully factorize all A*B/GCD(A,B)^2 numbers?

GCD calculation is fairly cheap but factorization is more expensive. Now since you're looking for the minimum distance it should be possible to quit a factorization as soon as it's established that the distance it represents is going to be longer than the current minumum distance. It won't change the O(N^2) complexity but it will reduce calculations substantially. Maybe it's enought to render your algorithm feasible for large N.

What's the background for this problem? Is there reason to assume that there's some deep number theoretical result available that could be used to lower the complexity of the algorithm you've come up with?
Last edited by nuzzle; November 8th, 2011 at 12:04 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•