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: 

    func Solution(N int) int

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

    package main
    import (
    	"fmt";
    )

    func Solution(N int) int {
        var i int = 1;
        var noFactors int = 0;

        for (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;
    }
    
    func main() {
        var ret int= Solution(24);
        fmt.Println(ret);
    }

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:

    func Solution(N int) int {
        var i int64 = 1;
        var noFactors int = 0;

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

Remember that at app.codility.com, the Go main function is not typed (not submitted). Before submitting, also delete '"fmt";' and replace "package main" with "package solution".

Thanks for reading.