Trovare il numero di coppie in cui il primo elemento è divisibile per secondo elemento

Question

suppongo, dato alcuni numeri

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

dovete trovare tutte le coppie in cui (a, b)a compare nella lista prima b e a%b = 0.

Ecco, queste coppie sono:

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

Esiste un algoritmo migliore di O (n)?

Answer 1

L'utilizzo della programmazione dinamica può essere risolto con la complessità O (nlogn). Simile al problema della denominazione della moneta.

prega di fare riferimento al seguente link per soluzione problema monete di taglio Coin Denomination problem

Answer 2

È possibile precompute un elenco di tutti i divisori dei possibili numeri interi in input = O (n^1.5)

Dopo di che un'iterazione su l'input, tenendo traccia di quanto vale un numero (cioè quante coppie si formerebbero).

per ogni numero in entrata è necessario iteratore su tutti i suoi divisori, cioè O (n^1.5)

Così la complessità totale è O (n^1.5) dove n è il massimo di 100000 e la dimensione del tuo contributo.

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;              
    }                  

}