Finding two pairs of numbers such that their products absolute difference is minimized

Question

Question:

Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.

Return the two integers in any order.

I tried this:

vector<int> closestDivisors(int num) {
    
    if(num == 1)
        return {1,2};
    int first = num + 1, second = num + 2;
    std::vector<int> result(2);        
    auto vec1 = properDivisors(first);
    auto vec2 = properDivisors(second);
    std::map<int, std::pair<int,int>> m;
    int min_k1 = INT_MAX;
    for(auto it1 : vec1)
    {
        for(auto it2 : vec1)
        {
            if (it1 * it2 == first)
            {
                min_k1 = abs(it1-it2);
                m[min_k1] = {it1, it2};
            }
        }
    }
    
    int min_k2 = INT_MAX;
    for(auto it1 : vec2)
    {
        for(auto it2 : vec2)
        {
            if (it1 * it2 == second)
            {
                min_k2 = abs(it1-it2);
                m[min_k2] = {it1, it2};
            }
        }
    }

    for(auto it : m)
    {
        result[0] = it.second.first;
        result[1] = it.second.second;
        if(result.size() == 2)
            break;
    }
    
    
    

    return result;
}


std::vector<long long> properDivisors(int number) {
   std::vector<long long> divisors ;
   for ( int i = 1 ; i < number / 2 + 1 ; i++ )
      if ( number % i == 0 )
     divisors.push_back( i ) ;
   return divisors ;
}

But I keep getting Time Limit Exceeded. Is there a more efficient way of achieving this?

Answer 1

Here is the code in c++.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
       if(v.size() - i == 1) {
           cout << v[i];
       } else {
          cout << v[i] << ", ";
       }
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector <int> getDiv(int x){
      int diff = INT_MAX;
      vector <int> ret(2);
      for(int i = 1; i * i <= x; i++){
         if(x % i == 0){
            int a = i;
            int b = x / i;
            int newDiff = abs(a - b);
            if(newDiff < diff){
               diff = newDiff;
               ret[0] = a;
               ret[1] = b;
            }
         }
      }
      return ret;
   }
   vector<int> closestDivisors(int num) {
      vector <int> op1 = getDiv(num + 1);
      vector <int> op2 = getDiv(num + 2);
      return abs(op1[0] - op1[1]) <= abs(op2[0] - op2[1]) ? op1 : op2;
   }
};
main(){
   Solution ob;
   print_vector(ob.closestDivisors(8));
}

// Output [3,3]

You can run the above code here

Reference.

Code in Javascript.

let num = 8; //Input

function getFactors(num) {
  let factors = [1];
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      factors.push(i);
      factors.push(num / i);
    }
  }
  factors.push(num);
  return factors;
}

(function getSmallAbsDiff() {
  const factorsNplusOne = getFactors(num + 1).sort((a, b) => a - b);
  const factorsNplusTwo = getFactors(num + 2).sort((a, b) => a - b);

  const minOne = factorsNplusOne[factorsNplusOne.length / 2 - 1];
  const maxOne = factorsNplusOne[factorsNplusOne.length / 2];
  const minTwo = factorsNplusTwo[factorsNplusTwo.length / 2 - 1];
  const maxTwo = factorsNplusTwo[factorsNplusTwo.length / 2];

  maxOne - minOne < maxTwo - minTwo ? console.log(`[${maxOne}, ${minOne}]`) : console.log(`[${maxTwo}, ${minTwo}]`); // Output
})();

Reference

Answer 2

The use of vectors is probably going to make it much slower than it needs to be. I would approach it as follows.

Set lo to 1 and hi to num + 1. This is the starting point for getting two integers that multiply out to one of the desired values (closer together then 1 and num + 2 so you can ignore that possibility).

Then simply move lo and hi toward each other (until they cross) checking the product to see if it's equal to a desired value. The fact that the two numbers are approaching means that any later success will have them closer together than the earlier ones.

The only tricky bit is how the numbers approach each other but this is simpler than you think. If the product is less than num + 1, decreasing hi will mean it gets further away from a desired value so you need to increase lo in that case.

On the other hand, the product being greater than num + 2 means you should decrease hi (increasing lo would move the product higher, hence further away from a desired value).

If it's equal to num + 1 or num + 2, you can choose either option. The reason it doesn't matter is because the absolute difference between lo + 1 and hi is the same as that between lo and hi -1^(a).

---

For example, here's a Python program that shows it in action:

num = int(input("Number: "))
lo = 1
hi = num + 1
found = None
while lo <= hi: # Make this '<' if numbers must be different.
    prod = lo * hi
    if prod == num + 1 or prod == num + 2:
        found = (lo, hi)
        mark = ' *'
    else:
        mark = ""
    print(f"Low = {lo}, high = {hi}, product = {prod}{mark}")
    if prod < num + 1:
        lo += 1
    else:
        hi -= 1
print(found)

Along with a couple of runs:

Number: 3
Low = 1, high = 4, product = 4 *
Low = 1, high = 3, product = 3
Low = 2, high = 3, product = 6
Low = 2, high = 2, product = 4 *
(2, 2)

Number: 10
Low = 1, high = 11, product = 11 *
Low = 1, high = 10, product = 10
Low = 2, high = 10, product = 20
Low = 2, high = 9, product = 18
Low = 2, high = 8, product = 16
Low = 2, high = 7, product = 14
Low = 2, high = 6, product = 12 *
Low = 2, high = 5, product = 10
Low = 3, high = 5, product = 15
Low = 3, high = 4, product = 12 *
Low = 3, high = 3, product = 9
(3, 4)

Number: 100
Low = 1, high = 101, product = 101 *
Low = 1, high = 100, product = 100
Low = 2, high = 100, product = 200
Low = 2, high = 99, product = 198
: : : (lots of stuff irrelevant to final result)
Low = 6, high = 18, product = 108
Low = 6, high = 17, product = 102 *
Low = 6, high = 16, product = 96
Low = 7, high = 16, product = 112
Low = 7, high = 15, product = 105
Low = 7, high = 14, product = 98
Low = 8, high = 14, product = 112
Low = 8, high = 13, product = 104
Low = 8, high = 12, product = 96
Low = 9, high = 12, product = 108
Low = 9, high = 11, product = 99
Low = 10, high = 11, product = 110
Low = 10, high = 10, product = 100
(6, 17)

---

As pointed out in a comment, this only handles positive inputs. You can cater for negative inputs as well by changing:

lo = 1
hi = num + 1

to:

lo = -num - 1
hi = num + 1
if lo > hi:
    (lo, hi) = (hi, lo)

This brackets the positive and negative realms for solutions, adding a little extra time but still pretty fast.

---

^(a) I'm only 99.99% sure of my mathematics here so, if anyone can provide a counter example, I'll be happy to edit the answer (or even delete it, if I can't fix it though any problems that exist are probably going to be found in the edge cases so will likely be fixable with some simple pre-checks). Let me know.