Given an even number N, the task is to find the greatest possible odd factor of N.
Examples:
Input: N = 8642
Output: 4321
Explanation:
Here, factors of 8642 are {1, 8642, 2, 4321, 29, 298, 58, 149} in which odd factors are {1, 4321, 29, 149} and the greatest odd factor among all odd factors is 4321.Input: N = 100
Output: 25
Explanation:
Here, factors of 100 are {1, 100, 2, 50, 4, 25, 5, 20, 10} in which odd factors are {1, 25, 5} and the greatest odd factor among all odd factors is 25.
Naive Approach: The naive approach is to find all the factors of N and then select the greatest odd factor from it.
Time Complexity: O(sqrt(N))
Efficient Approach: The efficient approach for this problem is to observe that every even number N can be represented as:
N = 2i*odd_number
Therefore to get the largest odd number we need to divide the given number N by 2 until N becomes an odd number.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include<bits/stdc++.h> using namespace std; // Function to print greatest odd factor int greatestOddFactor(int n) { int pow_2 = (int)(log(n)); // Initialize i with 1 int i = 1; // Iterate till i <= pow_2 while (i <= pow_2) { // Find the pow(2, i) int fac_2 = (2 * i); if (n % fac_2 == 0) { // If factor is odd, then // print the number and break if ((n / fac_2) % 2 == 1) { return (n / fac_2); } } i += 1; } } // Driver Code int main() { // Given Number int N = 8642; // Function Call cout << greatestOddFactor(N); return 0; } // This code is contributed by Amit Katiyar |
Java
// Java program for the above approachclass GFG{ // Function to print greatest odd factor public static int greatestOddFactor(int n) { int pow_2 = (int)(Math.log(n)); // Initialize i with 1 int i = 1; // Iterate till i <= pow_2 while (i <= pow_2) { // Find the pow(2, i) int fac_2 = (2 * i); if (n % fac_2 == 0) { // If factor is odd, then // print the number and break if ((n / fac_2) % 2 == 1) { return (n / fac_2); } } i += 1; } return 0;} // Driver codepublic static void main(String[] args){ // Given Number int N = 8642; // Function Call System.out.println(greatestOddFactor(N)); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach# importing Maths libraryimport math # Function to print greatest odd factordef greatestOddFactor(n): pow_2 = int(math.log(n, 2)) # Initialize i with 1 i = 1# Iterate till i <= pow_2 while i <= pow_2:# find the pow(2, i) fac_2 = (2**i) if (n % fac_2 == 0) : # If factor is odd, then print the # number and break if ( (n // fac_2) % 2 == 1): print(n // fac_2) break i += 1# Driver Code# Given NumberN = 8642# Function CallgreatestOddFactor(N) |
C#
// C# program for the above approachusing System;class GFG{ // Function to print greatest odd factor public static int greatestOddFactor(int n) { int pow_2 = (int)(Math.Log(n)); // Initialize i with 1 int i = 1; // Iterate till i <= pow_2 while (i <= pow_2) { // Find the pow(2, i) int fac_2 = (2 * i); if (n % fac_2 == 0) { // If factor is odd, then // print the number and break if ((n / fac_2) % 2 == 1) { return (n / fac_2); } } i += 1; } return 0;} // Driver codepublic static void Main(String[] args){ // Given number int N = 8642; // Function call Console.WriteLine(greatestOddFactor(N)); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// JavaScript program for the above approach// Function to print greatest odd factor function greatestOddFactor(n) { let pow_2 = (Math.log(n)); // Initialize i with 1 let i = 1; // Iterate till i <= pow_2 while (i <= pow_2) { // Find the pow(2, i) let fac_2 = (2 * i); if (n % fac_2 == 0) { // If factor is odd, then // print the number and break if ((n / fac_2) % 2 == 1) { return (n / fac_2); } } i += 1; } return 0;} // Driver Code // Given Number let N = 8642; // Function Call document.write(greatestOddFactor(N)); ; </script> |
4321
Time Complexity: O(log2(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
