PROBLEM STATEMENT
A number is called EVIL if it has an even number of 1's in its binary
expansion. If it has an odd number of 1's in its binary expansion, it is called
ODIOUS.
Your task is, given an int[], decide for each integer if it is evil or odious;
then return a String representing this int[] using 0 to represent an odious
number and 1 to represent an evil one.
If you're unsure how to convert from decimal to binary, see the explanation
after the EXAMPLES.
DEFINITION
Class: Evil
Method: evilness
Parameters: int[]
Returns: String
Method signature (be sure your method is public): String evilness(int[] num);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- num contains between 1 and 50 elements inclusive
- each element of num is an integer between 1 and 10000 inclusive
EXAMPLES
1. num = {1}, 1 is an odious number, hence the corresponding string is "0",
return "0"
2. num = {3,3,3,3}, decimal 3 corresponds to 11 in binary, hence 3 is an evil
number, hence the corresponding string is "1111", return "1111"
3. num = {1,2,4,8,3,5,9}, decimal numbers 1, 2, 4, and 8 correspond to binary
numbers 1, 10, 100, 1000 respectively, all of them have an odd number of ones,
hence all of them are odious; decimal numbers 3, 5, 9 correspond to binary
numbers 11, 101, 1001 respectively, hence all of them are evil; returns "0000111"
4. num = {16,32,64,128,256,512,1024,2048,4096,8192} returns "0000000000"
5. num = {1,3,7,15,31,63,127,255,511,1023,2047,4095,8191} returns "0101010101010"
BINARY 101:
This paragraph explains what a binary number is: How would we count if we could
only have two digits: 0 and 1? The beginning is easy. We could suggest that we
would denote 0 by 0 and 1 by 1. But what should we do next? In our regular
decimal notation we have many numbers which are written with 0's and 1's only.
What if we wrote down all of them one after another in increasing order? We
would get the following: 0, 1, 10, 11, 100, 101, 110, 111, 1000, etc. We can
use this sequence to represent numbers. That is, we would use '10' to represent
2, we would use '11' to represent 3, we would use '100' to represent 4 and so
on. These new numbers are called binary numbers. We say that 100 in binary is
equal to 4 in decimal notation. Also, we say that decimal number 7 is equal to
111 in binary notation. You can notice that 10 in binary represents decimal
number 2, 100 in binary represents decimal number 4, 1000 in binary represents
decimal number 8.
This paragraph explains how to convert a decimal number to binary. There are
two methods of converting decimals to binary. Here we present both methods
using the number 69 as an example. First method. We are trying to represent the
decimal number 69 as the sum of powers of two, starting from the largest. Find
the largest power of 2 which is not more than 69. It is 64 = 2^6. Subtract it:
69 - 2^6 = 5. The result will always be less than the power of two that was
subtracted (can you figure out why?). Now we need to represent 5 as the sum of
powers of 2. Continue as before: the largest power of two which is not more
then 5 is 4 = 2^2. Subtract it: 5 - 2^2 = 1. We can represent 1 as 2^0. We got
that 85 = 2^6 + 2^2 + 2^0. This is the same as: 85 = 1 * 2^6 + 0 * 2^5 + 0 *
2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0. The binary representation of 69 is
given by the coefficients in this representation listed one after another,
starting with the highest power of 2: 1000101.
Second method. This method is based on the observation that the last digit in
the binary representation is always the remainder of the number when divided by
two. That is, it is 1 if the number is odd, and 0 if it is even. If the last
number of the binary representation is 0 (hence the corresponding decimal
number is even) that means that if we crossed out this last digit we would get
the binary representation of our number divided by two. The number 69 is odd.
Hence, the last digit is 1. Subtract 1, we get 68. Then dividing 68 by 2 we get
34. Binary representation of 34 will get us all other digits to the left of the
last digit. The number 34 is even, hence its last binary digit is 0. Dividing
34 by 2 we get 17. 17's last binary digit is 1 (as it is odd). Subtract 1 and
divide by two again: we get 8. 8's last binary digit is 0. 8/2 = 4. 4's last
binary digit is 0. Then 4/2 = 2. 2's last binary digit is 0. Dividing 2 by 2,
we get 1, which represents the binary number 1. Write down the numbers you got
from right to left: 1000101.