Find Politeness of a Number in Java
Given n and, it is an integer. Determine the integer n's politeness. A number is considered polite if there are multiple ways to describe it as the sum of consecutive integers.
Example 1:
Input:
int n = 5
Output:
The politeness of a number is 1.
Explanation:
For the given number, the different ways in which consecutive integers obtain a sum are (2 + 3 = 5). Since there is only 1 way, the politeness of a number is 1.
Example 2:
Input:
int n = 12
Output:
The politeness of a number is 1.
Explanation:
For the given number, the different ways in which consecutive integers obtain sum are (4 + 5 + 6 = 12). Since there is 1 different way, the politeness of a number is 1.
Example 3:
Input:
int n = 15
Output:
The politeness of a number is 3.
Explanation:
For the given number, the different ways in which consecutive integers obtain the sum are (7 + 8 = 15; 4 + 5 + 6 = 15; 1 + 2 + 3 + 4 + 5 = 15). Since there are three ways, the politeness of a number is 3.
Approach: Efficient Solution with Factorization
We count the number of odd factors present after factorizing the integer n. The number of polite factors (except from 1) equals the total number of odd factors. See this for an example of this fact. Primitive factors of n are generally denoted by the notation ap * bq * cr, where a, b, c,... The total number of odd factors is [(q + 1) * (r + 1) * …] - 1 if a = 2 (even). If not, delete it and count the remaining odd factors. Since it is not permitted to have a single term in a representation, 1 is deducted here.
The fact is that the number of divisors is (p+1)*(q+1)*(r+1) if it is represented as ap * bq * cr, where a, b, c,... are prime factors of n. Let's simplify and assume that there is only one factor. The number is represented by ap. 1, a, a2,... ap are the divisors. P+1 is the number of divisors. Now, let's look at a little more complex example, apbp. The divisors are as follows: 1, a, a2,.. ap; b, ba, ba2,.. bap; b2, b2a, b2a2,.. b2ap; ....... bq, bqa, bqa2,.. bqap. The terms mentioned above have a count of (p+1)*(q+1). We can also demonstrate for more prime factors.
Let's take an example: the prime factor factorization for n = 90 is as follows:- => 2 * 32 * 51 = 90. The odd prime factors 3 and 5 have powers of 2 and 1, respectively. Utilize the following formula: (2 + 1)* (1 + 1) -1 = 5. Therefore, the answer will be 5. We can verify it twice.
Implementation:
FileName: PolitenessNumber.java
import java.io.*;
import java.util.*;
public class PolitenessNumber
{
// An algorithm to enumerate every
// odd prime factor of a given integer num
static int OddPrimeFactors(int num)
{
int res = 1;
// Delete every even prime factor of the number num.
while (num % 2 == 0)
num /= 2;
// At this point, num must be odd, thus
// repeat only for odd values till sqrt(num)
for (int i = 3; i * i <= num; i += 2)
{
int divCnt = 0;
// If i divide num, then the counting
// of odd divisors begins.
while (num % i == 0)
{
num /= i;
++divCnt;
}
res *= divCnt + 1;
}
// Check to determine whether
// there is still an odd prime.
if (num > 2)
res *= 2;
return res;
}
static int politeness(int num)
{
return OddPrimeFactors(num) - 1;
}
public static void main(String[] args)
{
int num = 12;
System.out.println("The Politeness of a given number is " + num + " = " + politeness(num));
}
}
Output:
The Politeness of a given number is 12 = 1
Complexity Analysis:
For the above code, the time complexity is O(sqrt(n)), and the space complexity is O(1).
Approach: Making use of AP
Determine the possibility of creating an AP for the length domain [2, sqrt(2*n)]. For AP 1, 2, and 3, the maximum length will be determined by calculating length till sqrt(2*n).
n= ( len * (len+1) ) / 2 = len2 + len - (2*n) = 0 is the length of this AP.
so len? sqrt(2*n) so that we can determine whether AP can be created with this len for any len from 1 to sqrt(2*n). Now, n= (len/2) * ( (2*A1) + len-1 is the formula to obtain the first term of the AP.
Algorithm:
Step 1: Initialize a number of integer type as, num.
Step 2: To count the politeness numbers, initialize a variable called cnt.
Step 3: Continue iterating from i = 2 to 2 * num squared.
Step 3.1: Go on to the following iteration if 2 * num is not divisible by i.
Step 3.2: Calculate an as 2 * num / i - (i - 1).
Step 3.3: Go on to the following iteration if an is odd.
Step 3.4: Divide a by two
Step 3.5: Increase cnt if an is greater than 0.
Step 4: Return the politeness number count back as the value of cnt.
Implementation:
FileName: APPolitenessNumber.java
import java.io.*;
import java.util.*;
import java.lang.Math;
public class APPolitenessNumber
{
static int politenessNumber(int num)
{
int cnt = 0;
// sqrt(2*n) as the maximum length will be
// when the sum begins at 1, which
// is in accordance with the
// equation num^2 - numm - (2*sum) = 0.
for (int i = 2; i <= Math.sqrt(2 * num); i++)
{
int a;
if ((2 * num) % i != 0)
{
continue;
}
a = 2 * num;
a /= i;
a -= (i - 1);
if (a % 2 != 0)
{
continue;
}
a /= 2;
if (a > 0)
{
cnt++;
}
}
return cnt;
}
public static void main(String[] args)
{
int num = 12;
System.out.println("The Politeness of a given number is " + num + " = " + politenessNumber(num));
}
}
Output:
The Politeness of a given number is 12 = 1
Complexity Analysis:
The time complexity and space complexity of the code is the same as the above code.