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: 

    class Solution { public 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):

    class Solution {
        public 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;
        }
    }

    public class temp {
        public static void main(String[] args) {
            Solution obj = new Solution();

            int ret = obj.solution(24);
            System.out.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:

    class Solution {
        public int solution(int n) {
            long 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.