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
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>
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