CODEWITHSUNDEEP
javaalgorithmmath
Cobbles
Cobbles

Reputation: 1798

Find closest factor to a number, of a number

I am trying to automate the finding of the closest factor of a number to another number;

Example:

Closest factor of 700 to 30 is 28 (30 does not go into 700, but 28 does).

An obvious solution is just to get all the factors of 700 and do a simple distance calculation to find the nearest factor to 30, but this seems to be inefficient.

Another solution is to find all the base prime factors, like:

private List<Integer> getPrimeFactors(int upTo) {
    List<Integer> result = new ArrayList<>();
    for (int i = 2; i <= upTo; i++) {
        if (upTo % i == 0) {
            result.add(i);
        }
    }
    return result;
}

And multiplying each of these numbers together to get all the combinations, and therefore find the closest.

I am trying to programme this so it is automated. Any better solutions?

Upvotes: 8

Views: 5658

Answers (5)

Cobbles
Cobbles

Reputation: 1798

I have my solution wrapped in a small static method:

/**
* @param target the number you want the factor to be close to
* @param number the number you want the result to be a factor of
*/
private static int getClosestFactor(int target, int number) {
    for (int i = 0; i < number; i++) {
        if (number % (target + i) == 0) {
            return target + i;
        } else if (number % (target - i) == 0) {
            return target - i;
        }
    }
    return number;
}

Upvotes: 1

Nuclearman
Nuclearman

Reputation: 5304

You can factorize the number, then use a powerset generator (for a multiset[1]) to search for the group of factors that get closest to the max without going over.

The powerset generator can be modified to prevent further iteration down branches that exceed the desired value (branch and bound). IE: if factors are (2,5,7,13,19). The number is 80, and you have 2*5*7 = 70. 2 * 5 * 7 * 13 = 910. There is no need to check 2 * 5 * 7 * 19 as it would clearly exceed the max.

[1] It's a good idea to treat the factorization as an multiset. For example in the case of 700, ((2,2),(5,2),(7,1)). You could treat it as (2,2,5,5,7), but it would do extra work since there's no need to find 2 * 5 = 10 more than once, but if it's not treated as a multiset, then that would happen.

Upvotes: 0

Udo
Udo

Reputation: 312

This should be a fast solution:

public static int findClosestFactor(int number, int closeTo) {
    int result = 1;
    int currentDist = closeTo - 1;
    // stop conditions for comparison
    boolean compareSmallFactor = true;
    boolean compareLargeFactor = true;
    for (int factor1 = (int) Math.sqrt(number); factor1 > 0; factor1--) {
        if (number % factor1 == 0) {
            if (compareSmallFactor) {
                int dist1 = Math.abs(closeTo - factor1);
                if (dist1 < currentDist) {
                    result = factor1;
                    currentDist = dist1;
                }
                // factor 1 is getting always smaller
                // so you need not compare next time, if go away from target (smaller than target)
                if (factor1 <= closeTo) {
                    compareSmallFactor = false;
                }
            }

            if (compareLargeFactor) {
                int factor2 = number / factor1;
                int dist2 = Math.abs(closeTo - factor2);
                if (dist2 < currentDist) {
                    result = factor2;
                    currentDist = dist2;
                }
                // factor 2 is getting always larger
                // so you need not compare next time, if go away from target (larger than target)
                if (factor2 >= closeTo) {
                    compareLargeFactor = false;
                }
            }

            // if both factors go away from target, you can cancel
            if (!compareSmallFactor && !compareLargeFactor) {
                break;
            }
        }
    }
    return result;
}

Upvotes: 0

Fanish
Fanish

Reputation: 27

    package dummy;

    public class test {

        public static void main(String[] args) {
            int factorOff = 700;
            int factorFrom = 30;
            for (int i = 2; i < factorOff; i++) {
                if (factorOff % (factorFrom + i) == 0) {
                    System.out.println(factorFrom + i);
                    i = factorOff;
                } else if (factorFrom - i > 1 && factorOff % (factorFrom - i) == 0) {
                    System.out.println(factorFrom - i);
                    i = factorOff;
                }
            }
        }
    }

Upvotes: 0

Aayush Rathore
Aayush Rathore

Reputation: 180

You don't need to calculate all factors, but you can go in both directions from the number to find its closest number which is the factor of given number

Pseduo code will be:

n= given number(dividend);
x= second number( whose closest number is required)
i=0;
if(n%x==0) print x;
else
while(true){
   if(n%(x-i)==0){
      print x-i
      break 
   }
   else if(n%(x+i)==0){
     print x+i;    
       break 
   }
   else i=i+1
}

Upvotes: 1

Related Questions