def __init__
def __init__

Reputation: 1066

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

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

output Array:{2,1,1,0,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]<<" ";
        }
    }

Upvotes: 5

Views: 795

Answers (3)

Zoso
Zoso

Reputation: 3465

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).

Upvotes: 2

גלעד ברקן
גלעד ברקן

Reputation: 23955

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).

Upvotes: 0

MBo
MBo

Reputation: 80287

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]

Upvotes: 1

Related Questions