Найти количество пар, где первый элемент делится на второй элемент

Question

Предположим, учитывая некоторые номера

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

вы должны найти все пары (a, b) где a появится в списке до того b и a%b = 0.

Здесь, такие пары:

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

Есть ли лучший алгоритм, чем О (п)?

Answer 1

Используя динамическое программирование, это можно решить со сложностью O (nlogn). Подобно проблеме деноминации монет.

Пожалуйста, обратитесь к следующей ссылке для решения проблемы монеты номинала Coin Denomination problem

Answer 2

Вы можете предвычисление списка всех делителей возможных чисел на входе = O (п^1,5)

После этого перебрать вход, при этом отслеживая, сколько стоит число (т. е. сколько пар оно образует).

Для каждого числа на входе вам нужно итератора над всеми его делителей, т.е. O (п^1,5)

Таким образом, общая сложность O (п^1,5) где п максимум 100000 и размер вашего ввода.

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

}