Check Evil Number in Java
What you’ll learn
- The definition of an evil number: even count of
1bits in binary. - A bitwise method and a division-by-two method in Java.
- Live preview, edge cases (
0, negatives), and interview tips.
Prerequisites
You only need basic Java loops and binary-bit intuition.
- Binary numbers and set-bit counting (popcount).
- Java loops plus bitwise or division-based digit extraction.
- Understanding parity (even/odd count).
Math definition
A nonnegative integer n is evil iff popcount(n) % 2 == 0. If odd, the number is odious.
Intuition and examples
Convert to binary and count 1-bits. Numbers like 3 (11), 5 (101), and 15 (1111) are evil because their count of ones is even.
What is an evil number?
A nonnegative integer n is evil if its binary representation contains an even number of 1 bits. Otherwise it is odious.
Examples: 0, 3, 5, 6, 9, 10, 12, 15 are evil.
Live preview
Nonnegative integers in JavaScript safe range. Same logic as Java examples.
Algorithm
Goal: decide if n has even popcount.
Count 1 bits
Use loop + n & 1 and right shift, or use Integer.bitCount(n).
Check parity
If count % 2 == 0, it is evil; otherwise odious.
📜 Pseudocode
function popcount(n): // n >= 0
c = 0
while n > 0:
c += (n mod 2)
n = floor(n / 2)
return c
function isEvil(n):
return (popcount(n) mod 2) == 0Bitwise popcount (single value)
Checks 15 using manual bit counting in Java.
public class Main {
static int countSetBits(int n) {
int count = 0;
int x = n;
while (x != 0) {
count += (x & 1);
x >>>= 1;
}
return count;
}
static boolean isEvil(int n) {
if (n < 0) return false;
return countSetBits(n) % 2 == 0;
}
public static void main(String[] args) {
int number = 15;
if (isEvil(number)) {
System.out.println(number + " is an Evil Number.");
} else {
System.out.println(number + " is not an Evil Number.");
}
}
}15 is an Evil Number.
Evil numbers in [1, 10]
Prints 3 5 6 9 10 using division-by-two bit extraction.
public class Main {
static boolean isEvilNonNegative(int num) {
int ones = 0;
int x = num;
while (x > 0) {
if (x % 2 == 1) ones++;
x /= 2;
}
return ones % 2 == 0;
}
public static void main(String[] args) {
System.out.println("Evil numbers in the range 1 to 10:");
for (int i = 1; i <= 10; i++) {
if (isEvilNonNegative(i)) {
System.out.print(i + " ");
}
}
System.out.println();
}
}Evil numbers in the range 1 to 10: 3 5 6 9 10
⏱️ Time and space complexity
| Operation | Time | Extra space |
|---|---|---|
Popcount of n | O(log n) | O(1) |
Scan [a,b] | O((b-a+1) log U) | O(1) |
Optimization tips
Built-in: use Integer.bitCount(n) when allowed.
Manual: bitwise shifting is usually faster than converting to a string.
Input scope: reject negatives up front when definition is nonnegative only.
Input/output examples
| Input n | Output |
|---|---|
15 | Evil number |
7 | Odious / not evil |
0 | Evil number |
Edge cases
Zero case
0 is evil because popcount is 0, and 0 is even.
Negative inputs
Usually excluded by the nonnegative definition used in interview problems.
Range limits
Stay within Java integer limits unless you intentionally switch to long.
Summary
- Evil numbers have an even count of
1bits in binary. - In Java, use manual bit counting or
Integer.bitCount. - Handle
0clearly and define whether negatives are allowed.
❓ FAQ
The complementary class is odious numbers: nonnegative integers whose binary representation has an odd number of 1 bits. The names are mathematical wordplay.
About the author
8 people found this page helpful