CODEWITHSUNDEEP
c++arrays
MickeyMoise
MickeyMoise

Reputation: 259

How do I find the number with the most divisors in an array?

I have to input numbers into an array and at the end get the number that has the most divisors, or if there are more numbers with the same amount, print out the first one.

Example: 4 numbers, 6 12 48 108. 108 has the most divisors, so this one needs to show up. if there were numbers after 108 with the same amount of divisors, 108 would have still been the only one to show up.

#include <iostream>

using namespace std;

int main()
{
    int n = 0, d, largestCnt = 0;
    int cntA=0, cntB=0;

    cout << "How many elements?\n";
    cin >> n;

    int* v = new int[n];

    for(int i=0; i<n; i++)
        cin >> v[i];

    for(int i=0; i<n; i++){
        for(d=2; d<v[i]/2; d++)
            if(v[i]%d==0)
            cntA++;
        for(d=2; d<v[i+1]/2; d++)
            if(v[i+1]%d==0)
            cntB++;
        if(cntA > largestCnt)
            largestCnt = cntA;
        if(cntB > largestCnt)
            largestCnt = cntB;
    }
    cout << largestCnt;

    return 0;
}

this is the most I've done the past 2 hours, and I can't get past it

EDIT:

#include <iostream>

using namespace std;

int main()
{
    int n = 0, d;
    int mostDivisors=0, number_with_most_divisors=0;
    int currentDivisors = 0;

    cout << "How many elements?\n";
    cin >> n;

    int* v = new int[n];

    for(int i=0; i<n; i++)
        cin >> v[i];

    number_with_most_divisors = v[0];
    
    for(d=2; d<=v[0]/2; d++){
        if(v[0]%d == 0)
            mostDivisors++;
    }
    for(int i=1; i<n; i++){
        for(d=2; d<=v[i]/2; d++)
            if(v[i]%d == 0)
                currentDivisors++;
                
        if(currentDivisors > mostDivisors){
            mostDivisors = currentDivisors;
            number_with_most_divisors = v[i];
        }
    }
    cout << number_with_most_divisors;
    return 0;
}

Upvotes: 0

Views: 1883

Answers (3)

Mayank Kashyap
Mayank Kashyap

Reputation: 19

#include <iostream>

int main() {
    int n = 0, max_divs = 0, count = 0, max_divs_index = 0;
    std::cin >> n;
    int *v = new int[n];
    for (int i = 0; i < n; ++i) std::cin >> v[i];
    for (int i = 0; i < n; ++i) {
        count = 0; // resetting count to 0 in each iteration
        for (int j = 2; j < v[i]/2; ++j)
            if (v[i] % j == 0) count++; // checking if the number is divisible by numbers between 1 and number itself/2 (1 and num/2 exclusive)
        if (count > max_divs) { // checking if current count is greater than the maximum divisors
            max_divs = count; // updating maximum divisors
            max_divs_index = i; // updating the index of array element with maximum divisors
        }
    }
    std::cout << v[max_divs_index];
    delete[] v;
    return 0;
}

Upvotes: 0

vmp
vmp

Reputation: 2420

Here is the algorithm of what you have to do:

  1. Count the number of divisors of the first element in array. Save this value in mostDivisors. Set number_with_most_divisors as the first element in the array.

  2. Start from the second element in array (position 1) and for each element, count how many divisors it has, save it in currentDivisors. If currentDivisors > mostDivisors then set mostDivisors to be equal to currentDivisors and update number_with_most_divisors to be the current element in the array.

  3. The result is number_with_most_divisors at the end of the loop.

UPDATE

You are forgetting to initialize currentDivisors for each element after the first loop:

for(int i=1; i<n; i++){
        currentDivisors = 0; // You forgot to put this line!
        for(d=2; d<=v[i]/2; d++)
            if(v[i]%d == 0)
                currentDivisors++;
                
        if(currentDivisors > mostDivisors){
            mostDivisors = currentDivisors;
            number_with_most_divisors = v[i];
        }

Upvotes: 1

Aven Desta
Aven Desta

Reputation: 2443

// function to count the divisors 
int countDivisors(int n) 
{ 
    int cnt = 0; 
    for (int i = 1; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            // If divisors are equal, 
            // count only one 
            if (n / i == i) 
                cnt++; 
  
            else // Otherwise count both 
                cnt = cnt + 2; 
        } 
    } 
    return cnt; 
}

You can loop to enter the numbers into an array

Upvotes: 0

Related Questions