Task score : 100% -  Correctness : 100% ; Performance : 100%

Detected time complexity : O(sqrt(N))

Lesson 10 at app.codility.com/programmers

The solution and its explanation are given below. 

Category of Article : Technology | Computers and Software | Algorithm

Problem

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M. 

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function: 

    int solution(int N);

that, given a positive integer N, returns the number of its factors. 

For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Write an efficient algorithm for the following assumptions: 

        N is an integer within the range [1..2,147,483,647].

Strategy

Use the sub-section, "Code for Counting Number of Factors in √n Time" in the lesson (Prime and Composite Numbers), for this problem. 

Smart Solution

A solution() function is in the following program (read the code and comments):

    #include <stdio.h>
    
    int solution(int n) {
        int i = 1;
        int noFactors = 0;

        while (i * i < n) {    //i is lower factor. Square root not included here
            if (n % i == 0) {
                noFactors = noFactors + 2;    // counting in 2's
            }
            i = i + 1;
        }
        if (i * i == n)
            noFactors += 1;   //adds square root once, if perfect square
        
        return noFactors;
    }

    int main(int argc, char **argv) 
    { 
        int ret = solution(24);
        printf("%i\n", ret);

        return 0; 
    }

 The output is:

    8 

At app.codility.com/programmers the scoring and detected time complexity for this solution() is:

    Task score : 92% -  Correctness : 100% ; Performance : 83%

    Detected time complexity : O(sqrt(N)) 

Why is performance not 100% ? The performance error is as follows:

Analysis summary

The following issues have been detected: timeout errors.

For example, for the input 2147483647 the solution exceeded the time limit of 6s. 

This means that the execution environment at app.codility.com/programmers could not handle sum or product with the upper integer limit of 2147483647.

The solution is to declare the iterator integer, i as a long int, because there is (i x i) whose result goes above the int limit. The following solution gives 100% performance as well as 100% correctness:

    #include <stdio.h>
    
    int solution(int n) {
        long int i = 1;
        int noFactors = 0;

        while (i * i < n) {    //i is lower factor. Square root not included at this point
            if (n % i == 0) {
                noFactors = noFactors + 2;    // counting in 2's
            }
            i = i + 1;
        }
        if (i * i == n)
            noFactors += 1;   //adds square root that occurs once, if perfect square
        
        return noFactors;
    }

Thanks for reading.