Mayor factor impar de un número par

Dado un número par N , la tarea es encontrar el mayor factor impar posible de N .

Ejemplos: 

Entrada: N = 8642 
Salida: 4321 
Explicación: 
Aquí, los factores de 8642 son {1, 8642, 2, 4321, 29, 298, 58, 149} en los que los factores impares son {1, 4321, 29, 149} y el mayor factor impar entre todos los factores impares es 4321.

Entrada: N = 100 
Salida: 25 
Explicación: 
Aquí, los factores de 100 son {1, 100, 2, 50, 4, 25, 5, 20, 10} en los que los factores impares son {1, 25, 5} y el mayor factor impar entre todos los factores impares es 25. 
 

Enfoque ingenuo: el enfoque ingenuo es encontrar todos los factores de N y luego seleccionar el factor impar más grande de él. 
Complejidad del tiempo: O(sqrt(N))

Enfoque eficiente: El enfoque eficiente para este problema es observar que todo número par N se puede representar como:  

N = 2i*odd_number

Por lo tanto, para obtener el número impar más grande, debemos dividir el número dado N por 2 hasta que N se convierta en un número impar.

A continuación se muestra la implementación del enfoque anterior:  

// 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 program for the above approach
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 code
public static void main(String[] args)
{
     
    // Given Number
    int N = 8642;
     
    // Function Call
    System.out.println(greatestOddFactor(N));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program for the above approach
 
# importing Maths library
import math
 
# Function to print greatest odd factor
def 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 Number
N = 8642
 
# Function Call
greatestOddFactor(N)

// C# program for the above approach
using 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 code
public static void Main(String[] args)
{
     
    // Given number
    int N = 8642;
     
    // Function call
    Console.WriteLine(greatestOddFactor(N));
}
}
 
// This code is contributed by gauravrajput1

<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

Complejidad del tiempo: O(log2(N))