Find the number of pairs where the first element is divisible by second element

Question

Suppose, given some numbers

8, 7, 6, 5, 4, 3, 2

you have to find all pairs (a, b) where a appears in the list before b, and a%b = 0.

Here, such pairs are:

(8, 4), (8, 2), (6, 3), (6, 2), (4, 2)

Is there any better algorithm than O(n²) ?

Answer 1

You can precompute a list of all divisors of the possible integers in the input = O(n^1.5)

After that iterate over the input, while keeping track of how much a number is worth (i.e. how many pairs it would form).

For every number in the input you'll need to iterator over all it's divisors, i.e. O(n^1.5)

So the total complexity is O(n^1.5) where n is the maximum of 100000 and the size of your input.

class Denominators {                                                        

    public static void main (String[] a) {                                  
        int maxValue = 100000;                                              
        int[] problemSet = {8, 7, 6, 5, 4, 3, 2};                           
        System.out.println (new Denominators().solve(problemSet, maxValue));
    }                                                                       


    int solve (int[] problemSet, int maxValue) {                            
        List<List<Integer>> divisors = divisors(maxValue);                  
        int[] values = new int[maxValue + 1];                               
        int result = 0;                                                     
        for (int i : problemSet) {                                          
            result += values[i];                                            
            for (int d : divisors.get(i)) {                                 
                values[d]++;                                                
            }                                                               
        }                                                                   
        return result;                                                      
    }                                                                       


    private List<List<Integer>> divisors (int until) {                      
        List<List<Integer>> result = new ArrayList<>();                     
        for (int i = 0; i <= until; i++) {                                  
            result.add (new ArrayList<Integer>());                          
        }                                                                   
        for (int i = 1; i * i <= until; i++) {                              
            for (int j = i; j * i <= until ; j++) {                         
                result.get (i * j).add(i);                                  
                if (i != j) result.get (i * j).add(j);                      
            }                                                               
        }                                                                   
        return result;                                                      
    }                                                                       

}