Count divisors of each element of an array

Question

Looks like I was wrong somewhere that made the program not run.

The input consists of a count and then that many numbers; the output is the number of divisors (including 1 and itself) for each element of the array.

Sample:

input 3 16 17 18
output 5 2 6

Code:

#include <bits/stdc++.h>
using namespace std;
int countDivisors(int a[], int n) {
     int cnt = 0;
     for(int j = 1; j <= sqrt(a[i]); j++) {
        if(a[i] % j == 0) {
          if(a[i] % j == j) {
            cnt++;
          }
          else {
             cnt = cnt + 2;
          }
      }
 }
 return cnt;
}

int main() {
    int n, i = 0;
    cin >> n;
    int a[n];
    for(;i < n; i++) {
        cin >> a[i];
    }
    cout << " " << countDivisors(a, n);
    return 0;
}

Answer 1

First of all, in your function you used 'i' but you didn't define it. and you just printed first element's divisors. I just changed your function and cout:

#include <bits/stdc++.h>
using namespace std;
void countDivisors(int a[], int n) {
     int cnt;
     for(int i = 0;i<n;i++){
        cnt = 0;
     //For example: 8 is a divisor of 16 but it's bigger than sqrt(16) = 4, so better to use x/2 for biggest number 
     for(int j = 1; j <= (a[i]/2); j++) {
        if(a[i] % j == 0) {
            cnt++;
      }
 }
 //Because a[i] is a divisors too:
 cnt++;
 cout<<" "<<cnt;
}
}

int main() {
    int n, i = 0;
    cin >> n;
    int a[n];
    for(;i < n; i++) {
        cin >> a[i];
    }
    countDivisors(a,n);
    return 0;
}

Answer 2

Simple math:

If you divide natural numbers x by y i.e x/y, the remainder is always smaller than y.

'%' in C++ gives the 'remainder' of such a division. So the line a[i] % j == j basically checks if some number divided by j gives the remainder j, which is not possible. I believe what you really want to check is if a[i] is a complete square of j.

So replace a[i] % j == j with j * j == a[i] and your problem is solved. Let's keep is simple and neat.

Note: a[i] / j == j might not do what you want to do since a[i] and j are integers and will undergo integer division, discarding any remainders. For example 10 % 3 = 3 but 3 * 3 is not 10.

Edit from the comments: You need one more loop enclosing all your j-loop code to iterate across all elements of the array you passed. Here is your code with the corrected loop:

int countDivisors(int a[], int n) {
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 1; j <= sqrt(a[i]); j++) {
            if(a[i] % j == 0) {
                if(a[i] % j == j) {
                    cnt++;
                }
                else {
                    cnt = cnt + 2;
                }
            }
        }
    }
    return cnt;
}

Hope this helps.

Answer 3

public class Solution {
    public ArrayList<Integer> solve(ArrayList<Integer> A) {

        ArrayList<Integer> result= new ArrayList<Integer>();

        for(int i=0; i<A.size(); i++){

            int count= getDivisorsCount(A.get(i));

            result.add(count);
        }


        return result;

        
    }

    public int getDivisorsCount(int num){

        int count=0;
        for(int i=1; i*i <= num ; i++){
            if(num % i==0){
                count++;
                if( i !=num/i){
                    count++;
                }
            }
        }


        return count;
    }
}