Last Updated: 16 Sep, 2021
Factors
Moderate
Asked in company
You are given an integer N. Your task is to find the sum of the total number of factors from 1 to N modulo 2. A number X is called a factor of K if K mod X is 0 (the remainder when K is divided by X is 0).
Example:-
N=3
Answer:- 1 ( 1 has 1 factor , 2 has 2 factors and 3 has 2 factors , so total 5 and 5 % 2 = 1).
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.
The first line of each test case contains an integer ‘N’.
Output Format :
For each test case, return the total number of factors of all the numbers from 1 to ‘N’ mod 2.
Note :
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10^3
1 <= N <= 10^9
Time Limit: 1 sec
Approaches
Find the factors of the numbers from 1 to N and sum them up and return the sum mod 2.
Algorithm:-
- Declare a variable named COUNT and initialize it with 0.
- Iterate from 1 to N. (Let the iterator be i).
- Iterate from 1 to sqrt N (Let the iterator be j).
- If i mod j is equal to 0,
- If i divided by j is equal to j, increment COUNT by 1.
- Else, increment the COUNT by 2.
- Update COUNT as COUNT mod 2.
- If i mod j is equal to 0,
- Iterate from 1 to sqrt N (Let the iterator be j).
- Return COUNT.
All numbers except perfect squares have an even number of factors. So we are only concerned with non-perfect squares. Find the number of perfect squares that lie between 1 to N. If the number of perfect squares is odd return 1 , else return 0.
Algorithm:-
- Declare a variable named COUNT and initialize it with 0.
- Update COUNT as sqrt(N) (We are finding out the number of perfect squares that lie between 1 to N).
- Update COUNT as COUNT mod 2.
- Return COUNT.