How to get all the divisible pairs in a range faster?-CodePudding

I have a function to compute all the divisible pairs in a given range [start, end] and I would like to know if there's a way to improve the performance of it.

Here is my current implementation in Kotlin:

fun getDivisiblePairsInRange(
    start: Int,
    end: Int,
    ignoreSelfDivision: Boolean = false,
): List<IntArray>
{
    if (start == 0) throw IllegalArgumentException("start parameter can't be 0")

    val oneOrZero = if (ignoreSelfDivision) 1.0 else 0.0

    val divisiblePairs = mutableListOf<IntArray>()

    for (numerator in start..end)
    {
        val optimizedEnd = ceil(sqrt(numerator - oneOrZero)).toInt()

        var divisorFromPreviousIteration = -1

        for (denominator in start..optimizedEnd)
        {
            if (numerator % denominator != 0 || denominator == divisorFromPreviousIteration) continue

            divisiblePairs  = intArrayOf(numerator, denominator)

            val secondDivisor = numerator / denominator

            if (!(ignoreSelfDivision && numerator == secondDivisor) && denominator != secondDivisor) divisiblePairs  = intArrayOf(numerator, secondDivisor)

            divisorFromPreviousIteration = secondDivisor
        }
    }

    return divisiblePairs
}

As you can see the time complexity is O(n^1.5) and there's an ignoreSelfDivision to avoid getting pairs like (a, a), but it's not relevant.

These are some outputs from concrete examples to better show how the function behaves:

(1, 3)  -> [[1, 1], [2, 1], [2, 2], [3, 1], [3, 3]]
(1, 5)  -> [[1, 1], [2, 1], [2, 2], [3, 1], [3, 3], [4, 1], [4, 4], [4, 2], [5, 1], [5, 5]]
(1, 8)  -> [[1, 1], [2, 1], [2, 2], [3, 1], [3, 3], [4, 1], [4, 4], [4, 2], [5, 1], [5, 5], [6, 1], [6, 6], [6, 2], [6, 3], [7, 1], [7, 7], [8, 1], [8, 8], [8, 2], [8, 4]]
(1, 10) -> [[1, 1], [2, 1], [2, 2], [3, 1], [3, 3], [4, 1], [4, 4], [4, 2], [5, 1], [5, 5], [6, 1], [6, 6], [6, 2], [6, 3], [7, 1], [7, 7], [8, 1], [8, 8], [8, 2], [8, 4], [9, 1], [9, 9], [9, 3], [10, 1], [10, 10], [10, 2], [10, 5]]

---------- UPDATE ----------

This is a faster version from @Dave adapted to Kotlin:

fun getDivisiblePairsInRangeFromDave(
    start: Int,
    end: Int,
    ignoreSelfDivision: Boolean = false,
): List<IntArray>
{
    var ratio = end / start
    var currentDenominator = start
    val divisiblePairs = mutableListOf<IntArray>()

    while (ratio >= 1)
    {
        for (multiple in 1..ratio)
        {
            val numerator = currentDenominator * multiple

            if (ignoreSelfDivision && currentDenominator == numerator) continue

            divisiblePairs  = intArrayOf(numerator, currentDenominator)
        }

        ratio = end /   currentDenominator
    }

    return divisiblePairs
}

CodePudding user response：

This is linear in the output.

Let's say end/start = r (integer division).

If r == 0 there are no solutions.

Otherwise, 1start, 2start, 3start, ..., rstart are all in your range.

ditto for start i until at some point r*(start i) is out of range at which point you can decrement r.

Repeat until r gets decremented to 1.

Ruby code:

def get_pairs(first_int, last_int)
  r = last_int / first_int
  pairs = []
  cur_int = first_int
  while r >= 1
    1.upto(r) do |mult|
      pairs.append([cur_int * mult, cur_int])
    end
    cur_int  = 1
    r = last_int / cur_int
  end
  return pairs.to_s
end



> get_pairs(1,3)
=> [[1, 1], [2, 1], [3, 1], [2, 2], [3, 3]]

get_pairs(1,5)
=> [[1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [2, 2], [4, 2], [3, 3], [4, 4], [5, 5]]

> get_pairs(1,8)
=> [[1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1], [2, 2], [4, 2], [6, 2], [8, 2], [3, 3], [6, 3], [4, 4], [8, 4], [5, 5], [6, 6], [7, 7], [8, 8]]

get_pairs(1,10)
=> [[1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1], [9, 1], [10, 1], [2, 2], [4, 2], [6, 2], [8, 2], [10, 2], [3, 3], [6, 3], [9, 3], [4, 4], [8, 4], [5, 5], [10, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 10]]

--- update: an example of a succinct approach ---

So this is succinct except that I'm expressing the output as long strings for clarity. For actual use, you could return pairs representing the multiple and the max integer in the range that can be multiplied by that mult and still be in range.

This is O(last_int / first_int), or linear in the number of different multiples. It could be further improved by treating 1 as a special case since everything can always be multiplied by 1 and still be in range, but I don't do that here.

def get_pairs_succinct(first_int, last_int)
  mult = 1
  summary = ""
  while last_int / mult >= first_int
    summary  = "max int we can multiply by #{mult} and still be in-range: #{last_int / mult}\n"
    mult  = 1
  end
  puts summary
end

get_pairs_succinct(1,3)
max int we can multiply by 1 and still be in-range: 3
max int we can multiply by 2 and still be in-range: 1
max int we can multiply by 3 and still be in-range: 1

size of output = 3 vs 5 non-succinct

> get_pairs_succinct(1,5)
max int we can multiply by 1 and still be in-range: 5
max int we can multiply by 2 and still be in-range: 2
max int we can multiply by 3 and still be in-range: 1
max int we can multiply by 4 and still be in-range: 1
max int we can multiply by 5 and still be in-range: 1

size of output = 5 vs 10 non-succinct

> get_pairs_succinct(1,8)
max int we can multiply by 1 and still be in-range: 8
max int we can multiply by 2 and still be in-range: 4
max int we can multiply by 3 and still be in-range: 2
max int we can multiply by 4 and still be in-range: 2
max int we can multiply by 5 and still be in-range: 1
max int we can multiply by 6 and still be in-range: 1
max int we can multiply by 7 and still be in-range: 1
max int we can multiply by 8 and still be in-range: 1

size of output = 8 vs 20 non-succinct

> get_pairs_succinct(1,10)
max int we can multiply by 1 and still be in-range: 10
max int we can multiply by 2 and still be in-range: 5
max int we can multiply by 3 and still be in-range: 3
max int we can multiply by 4 and still be in-range: 2
max int we can multiply by 5 and still be in-range: 2
max int we can multiply by 6 and still be in-range: 1
max int we can multiply by 7 and still be in-range: 1
max int we can multiply by 8 and still be in-range: 1
max int we can multiply by 9 and still be in-range: 1
max int we can multiply by 10 and still be in-range: 1

size of output = 10 vs 27 non-succinct

Lastly, if we try this for a larger range or a range farther from one, the differences become more dramatic. E.g., for the range (10, 100):

non-succinct: output is 201 pairs, vs succinct: same information in 10 rows and proportional computation.

> get_pairs_succinct(10, 100)
max int we can multiply by 1 and still be in-range: 100
max int we can multiply by 2 and still be in-range: 50
max int we can multiply by 3 and still be in-range: 33
max int we can multiply by 4 and still be in-range: 25
max int we can multiply by 5 and still be in-range: 20
max int we can multiply by 6 and still be in-range: 16
max int we can multiply by 7 and still be in-range: 14
max int we can multiply by 8 and still be in-range: 12
max int we can multiply by 9 and still be in-range: 11
max int we can multiply by 10 and still be in-range: 10