# Find the largest exponent x such that p^x evenly divides n

Write a method getExponent(n, p) that returns the largest exponent x such that px evenly divides n. If p ≤ 1 the method should return -1.

• getExponent(162, 3) returns 4 because 162 = 21∙ 34, therefore the value of x here is 4.
• if n is 27 and p is 3, return 3 because 33 divides 27 evenly but 34 does not.
• if n is 28 and p is 3, return 0 because 30 divides 28 evenly but 31 does not.
• if n is 280 and p is 7, return 1 because 71 divides 280 evenly but 72 does not.
• if n is -250 and p is 5, return 3 because 53 divides -250 evenly but 54 does not.
• if n is 18 and p is 1, return -1 because if p <= 1 the function returns -1.
• if n is 128 and p is 4, return 3 because 43 divides 128 evenly but 44 does not.

I wrote following code to test that result

public class Exponent {

public static void main(String args[]) {
int n = 27;
int p = 3;
System.out.println("result is: " + getExponent(n, p));
}

public static int getExponent(int n, int p) {
int count = 0;
if (p <= 1) {
count = -1;
} else {
boolean status = true;
while (status) {
if (n % p == 0) {
count++;
n = n / p;
} else {
status = false;
break;
}
}
}

return count;
}
}


I checked whether n is divisible by p or not. If divisible, then increment count and return count. Is this the right way to do that?

-
There are some more efficient ways to solve this problem. A slight clue, if p^x | n, we can check if p^2x | n. If it does, we need not test x, x + 1, .. 2x -1, 2x. If it doesn't, we can check if p^floor(1.5x) | n. (Binary search) – Lan Jan 19 at 14:05

The algorithm is right, but the flow control is clumsy:

• The special case of p ≤ 1 should trigger an immediate return.
• Flag variables suck. Don't set a variable that tells the program where to go, when you could just use the right keywords and loop conditions to go there.

Instead of count, I suggest using x, sticking to the terminology in the problem statement.

public static int getExponent(int n, int p) {
if (p <= 1) {
return -1;
}
int x = 0;
for (; n % p == 0; n /= p) {
x++;
}
return x;
}


Note that there is an implicit Exponent constructor. I suggest suppressing it by defining

private Exponent() {}

-
ok, it seems more prefect in case of flow control and define variable. – user3789184 Jan 19 at 7:18

I would do an "early exit" in the case $p \le 1$ and save an indentation level for the "main case":

if (p <= 1) {
return -1;
}


The status variable is not needed, the while-loop can be simplified to

int count = 0;
while (n % p == 0) {
count++;
n = n / p;
}


Your program should check if the input number $n$ is zero, otherwise it will run into an infinite loop in that case.

-

Despite the excellent answer by 200_success, I felt like posting my own answer, as this question reminded me of my own college days, Data Structures class.

Here's what I'd write as an answer:

// Problem: find the largest exponent x such that p^x evenly divides n
import java.util.Scanner;

class LargestExponent {

public static void main(String [] args) {
LargestExponent le = new LargestExponent();
le.callMethod();
}

private void callMethod() {
int n, p;
Scanner input = new Scanner(System.in);
System.out.print("Enter value of n: ");
n = input.nextInt();
System.out.print("Enter value of p: ");
p = input.nextInt();
System.out.println("Value of x is: " + this.getExponent(n, p));

}

private int getExponent(int number, int div) {
int x = 0;
if(div <= 1) return -1;
while(number%div == 0) {
x++;
number = number/div;
}
return x;
}

}

• Our professor always insisted on using a single return statement; I never really found out why. I guess he thought students will make excessive use of return. Here, however, we have to write one less else if there's a return, so why not? It reduces code clutter. In the class, this'd have gotten me a 3/5.

• Instead of hardcoded values, I have used a Scanner class. It's typically C-ish, but it ensures there are no hard-coded 'magic numbers'. And it makes it easy to carry out all those tests in the question without having to edit the code.

• The professor also discouraged the 'break the infinite loop' tendency. Instead he always had us break the loop through the while() condition. Better that way.

• I'm also curious why you used:

int n = 27;
int p = 3;
System.out.println("result is: " + getExponent(n, p));

System.out.println("result is: " + getExponent(27, 3)); would have been better.

-
One thing both of us didn't do is to account for the divisibility of 2. Since 2^0 is allowed, its contribution can be ignored. But in other cases you'll have to check divisibility of 2 first: n%2 == 0, and divide by 2 before calculating x. – cst1992 Jan 19 at 10:57
I don't see why 2 is a special case. Perhaps you are misinterpreting "evenly divides" to mean that the quotient must be even? It just means there is no remainder, nothing more. – Erick Wong Jan 19 at 21:28
first, i initialize n and p, but later i removed the declaration and initialization of n and p. Than, I directly passed the value as you mention System.out.println("result is: " + getExponent(27, 3));. – user3789184 Jan 20 at 3:19
@ErickWong Yes, that's exactly what I interpreted that to be. Also the fact that 162 is denoted as 2^1 * 3^4. I imagined 324, for example, would be represented as 2^2 * 3^4. – cst1992 Jan 20 at 5:12
@user3789184 The sole purpose of n and p here is to be passed to the method. The arguments are passed by value, meaning copies are made that are used in the method body. The original nand p are unchanged from the getExponent method. So it just wastes memory to assign values of n and p to a variable. An exception is when you have to declare them as constants similar to C's #define where you define them as const in the main public class. – cst1992 Jan 20 at 5:30

I'd like to point out two shortcomings of the assignment, that lead to bad code:

• getExponent is a terrible name. It doesn't describe at all what it does. (However to be honest, I can't think of a better name that wouldn't be far too long).
• It's usually a bad idea to have a function like this return a "valid" value (in the sense it's a valid integer) to indicate an error case, because it will wreck havoc, if the user forgets to catch it. Instead the method should throw an exception, or return null or an Optional.

And one other small thought: An alternative way to solve this problem (although most likely a slower, but IMO interesting way), would be to get the prime factors for the input arguments, and see how often the factors of p can be found in n. E.g., for getExponent(540, 6)`:

\begin{align*} 540 &= 2^2 \times 3^3 \times 5 \\ 6 &= 2^1 \times 3^1 \end{align*}

So both 2 and 3 (the factors of 6) can be found (at least) twice in the factors of 540, so the solution is 2.

-