This was one of the first problems in the set, and a relatively easy one that makes a good refresher on how booleans work. The sentence "boolean 'isDivisible' which resolves to true if the number is divisible by 6 and not 7 OR divisible by 7 and not 6" translates in code to "boolean isDivisable = ((integer % 6 == 0) && (integer % 7 != 0)) || ((integer % 7 == 0) && (integer % 6 != 0));"
How long it took: 20 min
What made it tough: Nada, not by now :)
Lingering questions: Is there a better way to do this? For example, what if you first found through all the numbers divisible by 6, then all the numbers divisible by 7, then de-duped them. Would that be any more efficient or flexible?
Also, my friend from work John Britton says that automated tests are a good practice. For a problem like this, you can imagine that if the range of numbers were much bigger (say 1-500,000), it would be harder to confirm that the code is accurate. How would you go about building in tests?
/*
* File: DivisibleBy6or7.java
* Name: Chu
* Section Leader:
* Description: This program finds the integers from 1 to 100 that are divisible by 6 or 7 (but not both) by running a boolean 'isDivisible' which resolves to true if the number is divisible by 6 and not 7 OR divisible by 7 and not 6. If the 'isDivisible' resolves to true, the we display the integer.
* ------------------
*/
package Ch4Practice;
import acm.program.*;
public class DivisibleBy6or7 extends ConsoleProgram {
public void run() {
println("These are the integers from 1 to 100 that are divisible by 6 or 7, but not both:");
for (int i = 1; i < 101; i++) {
int integer = i;
boolean isDivisable = ((integer % 6 == 0) && (integer % 7 != 0)) || ((integer % 7 == 0) && (integer % 6 != 0));
if(isDivisable) {
println(integer);
}
}
}
}
Good stuff -- it's getting easier and easier, no? :] Here's a new tool for you: the ^, or the "exclusive OR" (XOR). It's a "bitwise operator" that's perfectly suited for this task, i.e. it evaluates to true when exactly one of the operands is true (assuming booleans or single bits). There are more advanced uses, but for the purposes of this problem, you could use it like this to get the same result:
ReplyDelete// @ln 18:
boolean isDivisable = ((i % 6 == 0) ^ (i % 7 == 0));
This way, as well as your original solution, is definitely more efficient than finding both sets of multiples and de-duplifying. (Also note that line 17 becomes unnecessary, since i is already the number you care about.)
Another thing to note is that a number is divisible by two numbers if and only if it is divisible by the product of those numbers. I.e., numbers that are divisible by both 6 & 7 must also be divisible by 6*7. So here's another alternate line 18, without using ^:
boolean isDivisable = (i % (6*7) != 0) && ((i % 6 == 0) || (i % 7 == 0)); // IMPORTANT: (i % (6*7)) != (i % 6*7)
Hope this helps!
Now that you have done the coding, it's always a fun (and important) exercise to optimize. Can you think of ways to speed this up?
ReplyDeleteRight now your solution is on the order of O(n), which is not bad, but I can see you're looping through each number, so that can be improved. And there must be more!
Manus, what do you mean that the XOR operator is definitely more efficient? I can see that it's less code...but at runtime is it more efficient? You say that the exclusive OR is more efficient than finding both sets of multiples and de-duping, but doesn't the XOR operator do that implicitly under the hood?
ReplyDeleteHey Renee,
ReplyDeleteI'm going to arbitrarily pick this as my starting point for commenting. Your programs look really good - the years have made me nitpicky, so take my comments with a grain of salt. :)
This looks like a good solution, and I wouldn't worry too much about the XOR operator that manus mentions. It's good to know eventually, but you'll learn all about it in due time. :)
Nitpicks:
* The println under run() should be indented the same amount as the for loop. Having everything in the same scope indented by the same amount makes it easier to see how many times lines of code will execute and how long variables will stick around, so it's kind of pedantic to bring up, but it makes it quicker to read in the long run. Likewise, the println under isDivisable is indented by a weird amount.
* You probably want to get used to separating out hardcoded values into constants. For instance, in this case, you probably want to have:
private static final int MIN_VALUE = 0;
private static final int MAX_VALUE = 100;
...
for (int i = MIN_VALUE; i <= MAX_VALUE; i++) {
}
This comes in handy if you ever want to change the values. At the present time it doesn't really matter since they're only used once, but in a larger program, they'd probably be used many times, and making them a named constant means that you only have to change the value once.
That's all I've got for this one! I think manus pretty well covered the ways you can make it a bit simpler by using more advanced techniques.
Gh0st: There's no way to optimize this past O(n). You're fundamentally outputting O(n) numbers. You can make the case that keeping counters that advance by 6 and 7 would be faster than doing the modulus each time and that may be true, but that's still O(n). I definitely understand wanting to encourage people to think of optimization opportunities, but I don't think there's any low-hanging fruit given the tools in the Roberts book up to this point.
Thanks Fred! I'll take what you said about the 'println' and 'for' methods being in the same scope and therefore should be indented the same amount. The 'println' under 'if(isDivisable)' should be indented in by 4 spaces or 1 tab. For some reason my Eclipse (where I write this stuff) recognizes tabs, but when I paste the code in to Blogger, tabs get treated as spaces. Any way around that?
ReplyDeleteAh, I like the idea of iterating up to a constant that you hard code in; yes, much more flexible.