Find politeness of a number - GeeksforGeeks
Given an integer n. Find politeness of number n. Politeness of a number is defined as the number of ways it can be expressed as the sum of consecutive integers.
Read full article from Find politeness of a number - GeeksforGeeks
Given an integer n. Find politeness of number n. Politeness of a number is defined as the number of ways it can be expressed as the sum of consecutive integers.
Naive approach is to run a loop one inside another and find the sum of every consecutive integers up to n. Time complexity of this approach will be O(n2) which will not be sufficient for large value of n.
Efficient approach is to use factorization. We factorize the number n and count the number of odd factors. Total number of odd factors (except 1) is equal to politeness of the number. Refer this for proof of this fact. In general if a number can be represented as ap * bq * cr … where a, b, c, … are prime factors of n. If a = 2 (even) then discard it and count total number of odd factors which can be written as [(q + 1) * (r + 1) * …] – 1 (Here 1 is subtracted because single term in representation is not allowed).
How does above formula work? The fact is, if a number is expressed as ap * bq * cr … where a, b, c, … are prime factors of n, then number of divisors is (p+1)*(q+1)*(r+1) ……
To simplify, let there be one factor and number is expressed as ap. Divisors are 1, a, a2, …. ap. The count of divisors is p+1. Now let us take a slightly more complicated case apbp. The divisors are :
1, a, a2, …. ap
b, ba, ba2, …. bap
b2, b2a, b2a2, …. b2ap
…………….
…………….
bq, bqa, bqa2, …. bqap
To simplify, let there be one factor and number is expressed as ap. Divisors are 1, a, a2, …. ap. The count of divisors is p+1. Now let us take a slightly more complicated case apbp. The divisors are :
1, a, a2, …. ap
b, ba, ba2, …. bap
b2, b2a, b2a2, …. b2ap
…………….
…………….
bq, bqa, bqa2, …. bqap
The count of above terms is (p+1)*(q+1). Similarly, we can prove for more prime factors.
Illustration : For n = 90, decomposition of prime factors will be as follows:-
=> 90 = 2 * 32 * 51. The power of odd prime factors 3, 5 are 2 and 1 respectively. Apply above formula as: (2 + 1) * (1 + 1) -1 = 5. Hence 5 will be the answer. We can crosscheck it. All odd factors are 3, 5, 9, 15 and 45.
=> 90 = 2 * 32 * 51. The power of odd prime factors 3, 5 are 2 and 1 respectively. Apply above formula as: (2 + 1) * (1 + 1) -1 = 5. Hence 5 will be the answer. We can crosscheck it. All odd factors are 3, 5, 9, 15 and 45.
Time complexity: O(sqrt(n))
Auxiliary space: O(1)
Auxiliary space: O(1)
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
politness(
int
n)
{
return
countOddPrimeFactors(n) - 1;
}