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:

    function solution(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):

<script type='text/javascript'>
    "use strict";
    
    function solution(n) {
        let i = 1;
        let 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;
    }

    let ret = solution(24);
    document.write(ret + '<br>');
</script>

The output is:

    8

Thanks for reading.