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