CODEWITHSUNDEEP
javaalgorithm
Learner
Learner

Reputation: 21393

given an array for each element count how many divisibility

I have a list of numbers, now I want to take a number from the list and check how many elements are there that can divide this number with the remainder as 0.

Here is my code:

public static void countDivibilies(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        int e = list.get(i);
        int count = 0;
        for (int j = 0; j < list.size(); j++) {
            int k = list.get(j);
            if (e % k == 0) {
                count++;
            }
        }
        System.out.println(e + " : " + count);
    }
}

For sample input:

2, 4, 8, 2

Output is:

2 : 2
4 : 3
8 : 4
2 : 2

But this code runs in O(n2) time complexity. But my input list size range is up to 105, also each element is between 1 and 105. So how can improve the time complexity of this program?

Upvotes: 1

Views: 1055

Answers (2)

Ankit Pandey
Ankit Pandey

Reputation: 11

C++ code-

void countDivisibilities(vector<int> list) {
unordered_map<int, int> freq;
for (int x : list) freq[x]++;
for (int x : list) {
    int count = 0;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            count += freq[i];
            if (x / i != i) //don't overcount square root
                count += freq[x / i];
        }
    }
    cout << x << " : " << count << endl;
}

}

Upvotes: 0

Unmitigated
Unmitigated

Reputation: 89224

  1. Create a frequency Map in O(N) time from the List.
  2. Calculate divisors of each element of the List in O(sqrt(N)) time. Use the frequency Map to find how many divisors of the element are in the List. The total time complexity is O(Nsqrt(N)).
public static void countDivibilies(List<Integer> list) {
    Map<Integer, Integer> freq = list.stream()
       .collect(Collectors.toMap(x -> x, x -> 1, Integer::sum));
    for(int x : list){
        int count = 0;
        for(int i = 1; i * i <= x; i++){
            if(x % i == 0) {
                count += freq.getOrDefault(i, 0);
                if(x / i != i) //don't overcount square root
                   count += freq.getOrDefault(x / i, 0);
            }
        }
        System.out.println(x + " : " + count);
    }
}

Upvotes: 4

Related Questions