Factors

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in company
BirdEye

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
4
Sample Output 1 :
1
0
Explanation for Sample Output 1 :
In the first test case, 1 has 1 factor, 2 has 2 factors and 3 has 2 factors, so total of 5 factors and 5 % 2 = 1

In the second test case, 1 has 1 factor, 2 has 2 factors and 3 has 2 factors, 4 has 3 factors, so a total of 8 and 8 % 2 = 0
Sample Input 2 :
1
10
Sample Output 2 :
1
Hint

Calculate the number of factors of all the numbers from 1 to N.

Approaches (2)
Brute Force

Find the factors of the numbers from 1 to N and sum them up and return the sum mod 2.

 

Algorithm:-

 

  1. Declare a variable named COUNT and initialize it with 0.
  2. 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.
  3. Return COUNT.
Time Complexity

O(N*sqrt(N)), where N is the given input

 

We are iterating over every N numbers, and for every number, we are iterating sqrt(N) times, so the time complexity is O(N*sqrtN)).

Space Complexity

O(1)

We are using constant space here, so the space complexity is O(1).

Code Solution
(100% EXP penalty)
Factors
Full screen
Console