Given a number ānā, find its total number of divisors is even or odd.
Examples:
Input: n = 10 Output: Even Input: n = 100 Output: Odd Input: n = 125 Output: Even
A naive approach would be to find all the divisors and then see if the total number of divisors is even or odd. The time complexity for such a solution would be O(sqrt(n))Ā
Java
// Naive Solution to// find if count of// divisors is even// or oddimport java.io.*;import java.math.*;Ā
class GFG {Ā
Ā Ā Ā Ā // Function to countĀ Ā Ā Ā // the divisorsĀ Ā Ā Ā static void countDivisors(int n)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā // Initialize countĀ Ā Ā Ā Ā Ā Ā Ā // of divisorsĀ Ā Ā Ā Ā Ā Ā Ā int count = 0;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Note that thisĀ Ā Ā Ā Ā Ā Ā Ā // loop runs tillĀ Ā Ā Ā Ā Ā Ā Ā // square rootĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 1; i <= Math.sqrt(n) + 1; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (n % i == 0)Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // If divisors areĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // equal incrementĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // count by oneĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Otherwise incrementĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // count by 2Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā count += (n / i == i) ? 1 : 2;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā if (count % 2 == 0)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("Even");Ā
Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("Odd");Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Driver programĀ Ā Ā Ā public static void main(String args[])Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("The count of divisor:");Ā Ā Ā Ā Ā Ā Ā Ā countDivisors(10);Ā Ā Ā Ā }}/* This code is contributed by Nikita Tiwari.*/ |
The count of divisor: Even
Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)
Efficient Solution: We can observe that the number of divisors is odd only in case of perfect squares. Hence the best solution would be to check if the given number is perfect square or not. If itās a perfect square, then the number of divisors would be odd, else itād be even.Ā
Java
// Java program for// Efficient Solution to find// if count of divisors is// even or oddimport java.io.*;import java.math.*;Ā
class GFG {Ā
Ā Ā Ā Ā // Function to find if countĀ Ā Ā Ā // of divisors is even orĀ Ā Ā Ā // oddĀ Ā Ā Ā static void countDivisors(int n)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā int root_n = (int)(Math.sqrt(n));Ā
Ā Ā Ā Ā Ā Ā Ā Ā // If n is a perfect square,Ā Ā Ā Ā Ā Ā Ā Ā // then, it has odd divisorsĀ Ā Ā Ā Ā Ā Ā Ā if (root_n * root_n == n)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("Odd");Ā
Ā Ā Ā Ā Ā Ā Ā Ā elseĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("Even");Ā Ā Ā Ā }Ā
Ā Ā Ā Ā /* Driver program to test above function */Ā Ā Ā Ā public static void main(String args[])Ā Ā Ā Ā Ā Ā Ā Ā throws IOExceptionĀ Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("The count of "Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā + "divisors of 10 is: ");Ā
Ā Ā Ā Ā Ā Ā Ā Ā countDivisors(10);Ā Ā Ā Ā }}Ā
/* This code is contributed by Nikita Tiwari. */ |
The count of divisors of 10 is: Even
Time Complexity: O(log n), as the inbuilt sqrt() function is being used
Auxiliary Space: O(1), If we consider a recursive call stack then it would be O(log(n))
Please refer complete article on Check if count of divisors is even or odd for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
