Given an array,find the number of element it can divide or divided by the remaining elements of the array

user_13403510 0
Viewed 473
Input Array: int A={2,3,4,5,6} , array is not always sorted.

output Array:{2,1,1,0,2}
  • since we can see A[0] can divide 4 & 6 so it has output 2.
  • A[1] can divide only 6 ,it has output 1.
  • A[2] is divided by 2,so has output 1.
  • A[3] is not able to divide or being divided so has output 0.
  • A[4] is being divided by 2 & 3,so has output 2.

I'm able to solve it using brute force approach which has time complexity of o(n*n). what could be the most efficient way to solve it. thank you. my code:

    #include<iostream>
    #include<vector>
    using namespace std;
    //Function to return output vector
    vector<int>solve(vector<int> &A) {
        vector<int>v;
        for(int i=0;i<A.size();i++){
            int count=0;
            for(int j=0;j<A.size();j++){
                if(i!=j){
                    if(A[j]%A[i]==0 || A[i]%A[j]==0){
                        count++;
                    }
                }
            }
            v.push_back(count);
        }
        return v;
    }
    
    int main(){
        vector<int>v={2,3,4,5,6};
        vector<int>s;
        s=solve(v);
    //printing the output array
        for(int i=0;i<s.size();i++){
            cout<<s[i]<<" ";
        }
    }
dynamic-programming vector data-structures algorithm c++
3 Answers

I'm not sure if it's possible for your problem but how about something like

namespace {
    std::unordered_map<int, std::vector<size_t>> const factors{
        {1, {1}},
        {2, {1}},
        {3, {1}},
        {4, {1, 2}},
        {5, {1}},
        {6, {1, 2, 3}},
    };
}

std::vector<int>solve(std::vector<int> &A) {
    std::unordered_map<int, std::vector<size_t>> indexedFactors;
    size_t idx = 0;
    for(auto num: A) {
        // Lookup the factors of num from the table
       for(auto factor: factors.at(num)) {
           //  and add them to the map with indexes pointing to the number that has them as a factor
           indexedFactors[factor].push_back(idx);
       }
       ++idx;
    }
    std::vector<int> res(A.size());
    idx = 0;
    for(auto num: A) {
        if (indexedFactors.find(num) != indexedFactors.end()) {
            for(auto i: indexedFactors.at(num)) {
                res[i]++; // Track the divides
                res[idx]++; // Track the divided by
            }
        }
        ++idx;
    }
    return res;
}

You could have a pre-computed table of numbers and their factors (factors in the code). Don't have the number itself as a factor of itself added to the list.

Then you could iterate over the input array and add the factors of each number to a map and keep on adding the index of numbers of which they are a factor. e.g. If num is 6, then you add 1, 2, and 3 to the map with the index of 6 in the input array. Do this for all the numbers.

Now, iterate over the input array, and then for each number check if it's in the indexedFactors map and increment the count in the result array at all those indices. This takes care of the divides part. Also, increment the count for each of these times to take care of the divided by part. e.g. If num is 2 then it would have the indices of 4 and 6 within the input array, and these indices would be updated in the result array. But since 2 divides 4, 4 is divisible by 2 too, and hence increase the count in the result array at the index of 2.

The complexity is O(n * m) where m is the number of factors of each number in the input array (~ √num).

user_18516780

Simple modification helps to remove a half of iterations, but complexity remains quadratic.

It seems there is no way to solve this problem faster (with factorization etc)

 make v: vector of A.size zeros
 ...
      for(int j=i+1;j<A.size();j++){
         if(A[j]%A[i]==0 || A[i]%A[j]==0){
             increment v[i] and v[j]
user_8444160

For is divided by, reference a count of each element; find the divisors of each element and add the count of any matches.

For divides, reference a count of each seen divisor; add the count of any matches of the element.

O(n * sqrt m) where m is max(input).

user_20347870
Related