PROBLEM LINK:
Author: Varun Singh
DIFFICULTY:
CAKEWALK - SIMPLE
PREREQUISITES:
Math
PROBLEM:
Given a positive integer N, find the total number of factors of N.
QUICK EXPLANATION:
Loop till square root of the N, to count both factors in a single iteration. To take care of the corner case when N is a perfect square, increment the count only by 1.
EXPLANATION:
Counting the factors of the given integer using Brute Force will result in TLE, so we will exploit an interesting property of numbers. For a number N, it can be factored into two factors a and b (in case of prime, 1 and N itself). One of both factors is always less than or equal to the square root of N and the other is always greater than or equal to the square root. If both a and b were greater than the square root of N, (a*b) would be greater than N.
So we run our loop only till square root of N, and if i completely divides N, then i and N/i, both are factors, hence we increase the count by 2. If N is a perfect square, i and N/i will be equal, so for this iteration, we only increase the counter by 1.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.