Given a positive integer N, the task is to check if the given number N has at least 1 odd divisor from the range [2, N – 1] or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: N = 10
Output: Yes
Explanation:
10 has 5 as the odd divisor. Therefore, print Yes.Input: N = 8
Output: No
Approach: The idea to solve the given problem is to iterate through all possible odd divisors over the range [3, sqrt(N)] and if there exists any such divisor, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether N // has at least one odd divisor // not exceeding N - 1 or not string oddDivisor(int N) { // Stores the value of N int X = N; // Reduce the given number // N by dividing it by 2 while (N % 2 == 0) { N /= 2; } for (int i = 3; i * i <= X; i += 2) { // If N is divisible by // an odd divisor i if (N % i == 0) { return "Yes"; } } // Check if N is an odd divisor after // reducing N by dividing it by 2 if (N != X) return "Yes"; // Otherwise return "No"; } // Driver Code int main() { int N = 10; // Function Call cout << oddDivisor(N); return 0; } |
Java
/*package whatever //do not write package name here */import java.io.*; class GFG { // Function to check whether N // has at least one odd divisor // not exceeding N - 1 or not public static String oddDivisor(int N) { // Stores the value of N int X = N; // Reduce the given number // N by dividing it by 2 while (N % 2 == 0) { N /= 2; } for (int i = 3; i * i <= X; i += 2) { // If N is divisible by // an odd divisor i if (N % i == 0) { return "Yes"; } } // Check if N is an odd divisor after // reducing N by dividing it by 2 if (N != X) { return "Yes"; } // Otherwise return "No"; } // Driver Code public static void main(String[] args) { int N = 10; // Function Call System.out.println(oddDivisor(N)); } } // This code is contributed by aditya7409. |
Python3
# Python program for the above approach # Function to check whether N # has at least one odd divisor # not exceeding N - 1 or not def oddDivisor(N): # Stores the value of N X = N # Reduce the given number # N by dividing it by 2 while (N % 2 == 0): N //= 2 i = 3 while(i * i <= X): # If N is divisible by # an odd divisor i if (N % i == 0): return "Yes" i += 2 # Check if N is an odd divisor after # reducing N by dividing it by 2 if (N != X): return "Yes" # Otherwise return "No" # Driver Code N = 10# Function Call print(oddDivisor(N)) # This code is contributed by shubhamsingh10 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check whether N // has at least one odd divisor // not exceeding N - 1 or not public static string oddDivisor(int N) { // Stores the value of N int X = N; // Reduce the given number // N by dividing it by 2 while (N % 2 == 0) { N /= 2; } for (int i = 3; i * i <= X; i += 2) { // If N is divisible by // an odd divisor i if (N % i == 0) { return "Yes"; } } // Check if N is an odd divisor after // reducing N by dividing it by 2 if (N != X) { return "Yes"; } // Otherwise return "No"; } // Driver Code static public void Main() { int N = 10; // Function Call Console.Write(oddDivisor(N)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // javascript program for the above approach // Function to check whether N // has at least one odd divisor // not exceeding N - 1 or not function oddDivisor(N) { // Stores the value of N var X = N; var i; // Reduce the given number // N by dividing it by 2 while (N % 2 == 0) { N /= 2; } for (i = 3; i * i <= X; i += 2) { // If N is divisible by // an odd divisor i if (N % i == 0) { return "Yes"; } } // Check if N is an odd divisor after // reducing N by dividing it by 2 if (N != X) return "Yes"; // Otherwise return "No"; } // Driver Code var N = 10; // Function Call document.write(oddDivisor(N)); // This code is contributed by ipg2016107. </script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
