Lowest distance
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Lowest distance

  1. #1
    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. #2
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,012

    Re: Lowest distance

    Quote Originally Posted by boost View Post
    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)?
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  3. #3
    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. #4
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,012

    Re: Lowest distance

    Quote Originally Posted by boost View Post
    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.
    Quote Originally Posted by boost View Post
    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.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  5. #5
    Join Date
    May 2009
    Posts
    2,413

    Re: Lowest distance

    Quote Originally Posted by boost View Post
    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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center