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

<?php
    function solution($n) {
        $i = 1;
        $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;
    }

    $ret = solution(24);
    echo $ret . "\n";
?>

The output is:

    8

Thanks for reading.