Encuentra la cortesía de un número

Dado un entero n. Encuentra la cortesía del número n . La cortesía de un número se define como el número de formas en que se puede expresar como la suma de enteros consecutivos. 

Ejemplos:

Input: n = 15
Output: 3
Explanation:
There are only three ways to express
15 as sum of consecutive integers i.e.,
15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
Hence answer is 3

Input: n = 9;
Output:  2
There are two ways of representation:
9 = 2 + 3 + 4
9 = 4 + 5
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Enfoque ingenuo:

Ejecute un ciclo uno dentro de otro y encuentre la suma de cada entero consecutivo hasta n. La complejidad temporal de este enfoque será O(n 2 ), que no será suficiente para valores grandes de n.

Enfoque eficiente :

Utilice la factorización. Factorizamos el número n y contamos el número de factores impares. Un número total de factores impares (excepto 1) es igual a la cortesía del número. Consulte esto como prueba de este hecho. En general, si un número se puede representar como a p * b q * c r … donde a, b, c,… son factores primos de n. Si a = 2 (par), deséchelo y cuente el número total de factores impares que se pueden escribir como [(q + 1) * (r + 1) * …] – 1 (Aquí se resta 1 porque el término único en la representación es No permitido). 
¿Cómo funciona la fórmula anterior? El hecho es que si un número se expresa como a p * b q * c r… donde a, b, c, … son factores primos de n, entonces un número de divisores es (p+1)*(q+1)*(r+1) …… Para simplificar, sea un factor, 
y el número se expresa como p . Los divisores son 1, a, a 2 , …. una pág . La cuenta de divisores es p+1. Ahora tomemos un caso un poco más complicado a p b p . Los divisores son : 
1, a, a 2 , …. a p 
b, ba, ba 2 , …. ba p 
b 2 , b 2 a, b 2 a 2 , …. b 2 a p 
……………. 
……………. 
segundo q , segundoq a, b q a 2 , …. b q a p
La cuenta de los términos anteriores es (p+1)*(q+1). De manera similar, podemos probar para más factores primos.
Ilustración: Para n = 90, la descomposición de los factores primos será la siguiente:- 
=> 90 = 2 * 3 2 * 5 1 . El poder de los factores primos impares 3, 5 son 2 y 1 respectivamente. Aplique la fórmula anterior como: (2 + 1) * (1 + 1) -1 = 5. Por lo tanto, 5 será la respuesta. Podemos cotejarlo. Todos los factores impares son 3, 5, 9, 15 y 45.
A continuación se muestra el programa de los pasos anteriores:

C++

// C+ program to find politeness of number
#include <iostream>
using namespace std;
 
// A function to count all odd prime factors
// of a given number n
int countOddPrimeFactors(int n)
{
    int result = 1;
 
    // Eliminate all even prime
    // factor of number of n
    while (n % 2 == 0)
        n /= 2;
 
    // n must be odd at this point,
    // so iterate for only
    // odd numbers till sqrt(n)
    for (int i = 3; i * i <= n; i += 2) {
        int divCount = 0;
 
        // if i divides n, then start counting of
        // Odd divisors
        while (n % i == 0) {
            n /= i;
            ++divCount;
        }
 
        result *= divCount + 1;
    }
 
    // If n odd prime still remains then count it
    if (n > 2)
        result *= 2;
 
    return result;
}
 
int politeness(int n)
{
    return countOddPrimeFactors(n) - 1;
}
 
// Driver program to test above function
int main()
{
    int n = 90;
    cout << "Politeness of " << n << " = "
         << politeness(n) << "\n";
 
    n = 15;
    cout << "Politeness of " << n << " = "
         << politeness(n) << "\n";
    return 0;
}

Java

// Java program to find politeness of a number
 
public class Politeness {
    // A function to count all odd prime factors
    // of a given number n
    static int countOddPrimeFactors(int n)
    {
        int result = 1;
 
        // Eliminate all even prime
        // factor of number of n
        while (n % 2 == 0)
            n /= 2;
 
        // n must be odd at this point, so iterate
        // for only odd numbers till sqrt(n)
        for (int i = 3; i * i <= n; i += 2) {
            int divCount = 0;
 
            // if i divides n, then start counting of
            // Odd divisors
            while (n % i == 0) {
                n /= i;
                ++divCount;
            }
 
            result *= divCount + 1;
        }
        // If n odd prime still remains then count it
        if (n > 2)
            result *= 2;
 
        return result;
    }
 
    static int politeness(int n)
    {
        return countOddPrimeFactors(n) - 1;
    }
 
    public static void main(String[] args)
    {
        int n = 90;
        System.out.println("Politeness of " + n + " = "
                           + politeness(n));
 
        n = 15;
        System.out.println("Politeness of " + n + " = "
                           + politeness(n));
    }
}
 
// This code is contributed by Saket Kumar

Python3

# Python program to find politeness of number
 
# A function to count all odd prime factors
# of a given number n
def countOddPrimeFactors(n) :
    result = 1;
  
    # Eliminate all even prime factor of
    # number of n
    while (n % 2 == 0) :
        n //= 2
  
    # n must be odd at this point, so iterate
    # for only odd numbers till sqrt(n)
    i = 3
    while i * i <= n :
        divCount = 0
  
        # if i divides n, then start counting
        # of Odd divisors
        while (n % i == 0) :
            n //= i
            divCount = divCount + 1
        
        result = result * divCount + 1
        i = i + 2
  
    # If n odd prime still remains then count it
    if (n > 2) :
        result = result * 2
         
    return result
     
  
def politeness( n) :
    return countOddPrimeFactors(n) - 1;
 
# Driver program to test above function
n = 90
print ("Politeness of ", n, " = ", politeness(n))
n = 15
print ("Politeness of ", n, " = ", politeness(n))
 
# This code is contributed by Nikita Tiwari.

C#

// C# program to find politeness of a number.
using System;
 
public class GFG {
     
    // A function to count all odd prime
    // factors of a given number n
    static int countOddPrimeFactors(int n)
    {
         
        int result = 1;
 
        // Eliminate all even prime factor
        // of number of n
        while (n % 2 == 0)
            n /= 2;
 
        // n must be odd at this point, so
        // iterate for only odd numbers
        // till sqrt(n)
        for (int i = 3; i * i <= n; i += 2)
        {
            int divCount = 0;
 
            // if i divides n, then start
            // counting of Odd divisors
            while (n % i == 0) {
                n /= i;
                ++divCount;
            }
 
            result *= divCount + 1;
        }
         
        // If n odd prime still remains
        // then count it
        if (n > 2)
            result *= 2;
 
        return result;
    }
 
    static int politeness(int n)
    {
        return countOddPrimeFactors(n) - 1;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 90;
        Console.WriteLine("Politeness of "
               + n + " = " + politeness(n));
 
        n = 15;
        Console.WriteLine("Politeness of "
               + n + " = " + politeness(n));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find
// politeness of number
 
// A function to count all
// odd prime factors of a
// given number n
function countOddPrimeFactors($n)
{
    $result = 1;
 
    // Eliminate all even prime
    // factor of number of n
    while($n % 2 == 0)
        $n /= 2;
 
    // n must be odd at this
    // point, so iterate for only
    // odd numbers till sqrt(n)
    for ($i = 3; $i * $i <= $n; $i += 2)
    {
        $divCount = 0;
 
        // if i divides n, then
        // start counting of
        // Odd divisors
        while($n % $i == 0)
        {
            $n /= $i;
            ++$divCount;
        }
 
        $result *= $divCount + 1;
    }
 
    // If n odd prime still
    // remains then count it
    if ($n > 2)
        $result *= 2;
 
    return $result;
}
 
function politeness($n)
{
    return countOddPrimeFactors($n) - 1;
}
 
    // Driver Code
    $n = 90;
    echo "Politeness of " , $n , " = "
               , politeness($n), "\n";
 
    $n = 15;
    echo "Politeness of " , $n , " = "
               , politeness($n) ,"\n";
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
// JavaScript program for the above approach
  
    // A function to count all odd prime
    // factors of a given number n
    function countOddPrimeFactors(n)
    {
          
        let result = 1;
  
        // Eliminate all even prime factor
        // of number of n
        while (n % 2 == 0)
            n /= 2;
  
        // n must be odd at this point, so
        // iterate for only odd numbers
        // till sqrt(n)
        for (let i = 3; i * i <= n; i += 2)
        {
            let divCount = 0;
  
            // if i divides n, then start
            // counting of Odd divisors
            while (n % i == 0) {
                n /= i;
                ++divCount;
            }
  
            result *= divCount + 1;
        }
          
        // If n odd prime still remains
        // then count it
        if (n > 2)
            result *= 2;
  
        return result;
    }
  
    function politeness(n)
    {
        return countOddPrimeFactors(n) - 1;
    }
 
// Driver Code
     let n = 90;
        document.write("Politeness of "
               + n + " = " + politeness(n) + "<br />");
  
        n = 15;
        document.write("Politeness of "
               + n + " = " + politeness(n));
 
// This code is contributed by splevel62.
</script>
Output:
Politeness of 90 = 5
Politeness of 15 = 3

Complejidad temporal: O(sqrt(n)) 
Espacio auxiliar: O(1)
Referencia: Wikipedia

Otro enfoque eficiente :

Calcule si se puede generar un AP para el dominio de longitud dado [2, sqrt(2*n)]. La razón para calcular la longitud hasta sqrt (2 * n) es:

la longitud máxima será para el AP 1, 2, 3…

Length for this AP is -

n= ( len * (len+1) ) / 2

len2 + len - (2*n) =0

so len≈sqrt(2*n) 

por lo que podemos verificar para cada len de 1 a sqrt (2 * n), si se puede generar AP con este len. La fórmula para obtener el primer término del AP es:

n= ( len/2) * ( (2*A1) + len-1 )

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

C++

// CPP program for the above approach
#include <iostream>
#include <math.h>
using namespace std;
 
// Function to find politeness
int politness(int n)
{
    int count = 0;
   
    // sqrt(2*n) as max length
    // will be when the sum starts
    // from 1
    // which follows the equation n^2 - n - (2*sum) = 0
    for (int i = 2; i <= sqrt(2 * n); i++) {
        int a;
        if ((2 * n) % i != 0)
            continue;
        a = 2 * n;
        a /= i;
        a -= (i - 1);
        if (a % 2 != 0)
            continue;
        a /= 2;
        if (a > 0) {
            count++;
        }
    }
    return count;
}
 
// Driver program to test above function
int main()
{
    int n = 90;
    cout << "Politness of " << n << " = " << politness(n)
         << "\n";
 
    n = 15;
    cout << "Politness of " << n << " = " << politness(n)
         << "\n";
    return 0;
}
 
// This code is contributed by Prajjwal Chittori

Java

// Java program for the above approach
import java.lang.Math;
public class Main {
   
  // Function to find politeness
  static int politness(int n)
  {
    int count = 0;
 
    // sqrt(2*n) as max length
    // will be when the sum
    // starts from 1
    // which follows the
    // equation n^2 - n - (2*sum) = 0
    for (int i = 2; i <= Math.sqrt(2 * n); i++) {
      int a;
      if ((2 * n) % i != 0)
        continue;
      a = 2 * n;
      a /= i;
      a -= (i - 1);
      if (a % 2 != 0)
        continue;
      a /= 2;
      if (a > 0) {
        count++;
      }
    }
    return count;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int n = 90;
    System.out.println("Politness of " + n + " = "
                       + politness(n));
 
    n = 15;
    System.out.println("Politness of " + n + " = "
                       + politness(n));
  }
}
 
// This code is contributed by Prajjwal Chittori

Python3

# python program for the above approach
import math
 
# Function to find politeness
def politness(n):
    count = 0
     
    # sqrt(2*n) as max length will be
    # when the sum starts from 1
    # which follows the equation
    # n^2 - n - (2*sum) = 0
    for i in range(2, int(math.sqrt(2 * n)) + 1):
        if ((2 * n) % i != 0):
            continue
        a = 2 * n
        a = a // i
        a = a - (i - 1)
        if (a % 2 != 0):
            continue
        a //= 2
        if (a > 0):
            count = count + 1
    return count
 
 
# Driver program to test above function
n = 90
print ("Politness of ", n, " = ", politness(n))
n = 15
print ("Politness of ", n, " = ", politness(n))
 
# This code is contributed by Prajjwal Chittori

C#

// C# program for the above approach
using System;
public class GFG {
   
  // Function to find politeness
  static int politness(int n)
  {
    int count = 0;
 
    // sqrt(2*n) as max length
    // will be when the sum
    // starts from 1
    // which follows the
    // equation n^2 - n - (2*sum) = 0
    for (int i = 2; i <= Math.Sqrt(2 * n); i++) {
      int a;
      if ((2 * n) % i != 0)
        continue;
      a = 2 * n;
      a /= i;
      a -= (i - 1);
      if (a % 2 != 0)
        continue;
      a /= 2;
      if (a > 0) {
        count++;
      }
    }
    return count;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int n = 90;
    Console.WriteLine("Politness of " + n + " = "
                       + politness(n));
 
    n = 15;
    Console.WriteLine("Politness of " + n + " = "
                       + politness(n));
  }
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// JavaScript program for the above approach
 
  // Function to find politeness
 function politness(n)
  {
    let count = 0;
 
    // sqrt(2*n) as max length
    // will be when the sum
    // starts from 1
    // which follows the
    // equation n^2 - n - (2*sum) = 0
    for (let i = 2; i <= Math.sqrt(2 * n); i++) {
      let a;
      if ((2 * n) % i != 0)
        continue;
      a = 2 * n;
      a = Math.floor(a / i);
      a -= (i - 1);
      if (a % 2 != 0)
        continue;
      a = Math.floor(a / 2);
      if (a > 0) {
        count++;
      }
    }
    return count;
  }
 
// Driver Code
 
     let n = 90;
    document.write("Politness of " + n + " = "
                       + politness(n) + "<br/>");
 
    n = 15;
    document.write("Politness of " + n + " = "
                       + politness(n));
 
</script>
Producción

Politness of 90 = 5
Politness of 15 = 3

 Complejidad del tiempo : O(raíz cuadrada(2*n)) ≈ O(raíz cuadrada(n))                                                                                                                     

 Espacio auxiliar: O(1)                                                                                                                                                      

Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *