ISC Practicals and Theory - Evil Number (Recursive Technique)

An Evil Number is a positive whole number that has an even number of 1s in its binary (base-2) form. This version finds the binary form using recursion: a method rec_bin(int n) that calls itself until nothing is left to convert.

Definition

A positive integer $N$ is an Evil Number if the count of 1s in its binary equivalent is even. For example, $9 = 1001_2$ has two 1s, so 9 is an Evil Number. $7 = 111_2$ has three 1s, so 7 is not Evil (it is an Odious Number).

Algorithm

1. acceptNum() reads the number into num and sets valid to true only when num > 0.
2. If valid is false, display() prints INVALID INPUT and nothing else is done.
3. Otherwise main calls the recursive method rec_bin(num) and stores the result in bin. The method works like this:
   • Base case: if n == 0, return 0 (no digits left).
   • Recursive case: the last binary digit is n % 2. The digits before it are the binary form of n / 2, which rec_bin(n / 2) returns. Return rec_bin(n / 2) * 10 + n % 2.
4. countOnes() goes through the digits of bin. While b > 0: if b % 10 is 1, increase count; then drop the last digit with b = b / 10.
5. display() prints the binary equivalent and the number of 1s. If count % 2 == 0 it says the number is an Evil Number, otherwise it says it is not.

Program

acceptNum() reads and validates, rec_bin() builds the binary form recursively, countOnes() counts its 1s and display() prints the result.

import java.util.Scanner;

public class Evil
{
    int num;        // the number entered by the user
    long bin;       // the binary equivalent of num, written as a number of 0s and 1s
    int count;      // how many 1s there are in the binary form
    boolean valid;  // whether num is a positive number

    // Step 1: read the number from the user
    public void acceptNum()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        num = sc.nextInt();
        valid = (num > 0);    // only positive numbers can be Evil
    }

    // Recursive method: returns the binary equivalent of n as a number.
    // Base case: when n becomes 0 there are no more digits, so return 0.
    // Otherwise the last binary digit is n % 2, and the digits before it
    // are the binary form of n / 2 (the recursive call). Shifting those
    // digits one place left (multiplying by 10) and adding the last digit
    // joins them together.
    public long rec_bin(int n)
    {
        if (n == 0)
            return 0;
        return rec_bin(n / 2) * 10 + n % 2;
    }

    // Count the 1s in the binary form by taking out its digits one by one
    public void countOnes()
    {
        long b = bin;    // work on a copy, so bin is still there for display()
        count = 0;
        while (b > 0)
        {
            if (b % 10 == 1)    // this binary digit is a 1
                count++;
            b = b / 10;         // drop that digit and move to the next one
        }
    }

    // Show the binary form and say whether the number is Evil
    public void display()
    {
        if (!valid)
        {
            System.out.println("INVALID INPUT");
            return;
        }
        System.out.println("Binary equivalent = " + bin);
        System.out.println("Number of 1s = " + count);
        if (count % 2 == 0)
            System.out.println(num + " IS AN EVIL NUMBER");
        else
            System.out.println(num + " IS NOT AN EVIL NUMBER");
    }

    public static void main(String args[])
    {
        Evil ob = new Evil();
        ob.acceptNum();
        if (ob.valid)
        {
            ob.bin = ob.rec_bin(ob.num);
            ob.countOnes();
        }
        ob.display();
    }
}

Variable description table

Sample input and output

Enter a number: 9
Binary equivalent = 1001
Number of 1s = 2
9 IS AN EVIL NUMBER

Enter a number: 7
Binary equivalent = 111
Number of 1s = 3
7 IS NOT AN EVIL NUMBER

Enter a number: -5
INVALID INPUT

Dry run

Input: num = 9

First rec_bin(9) keeps calling itself until n is 0, then each call returns its answer to the one before it.

So bin = 1001. Now countOnes() runs on it:

The loop ends (b = 0). count = 2, which is even, so the output is 9 IS AN EVIL NUMBER.

Variations

1. Odious Number: "Accept a number and use a recursive method to find its binary equivalent. Check whether it is an Odious Number, that is, one with an odd number of 1s."
2. Both classifications: "Accept a number and state whether it is an Evil Number or an Odious Number, using a recursive method for the binary form."
3. Range-validated input: "Accept a positive integer $N$ with $1 \le N \le 1000$. If $N$ is outside the range, display INVALID INPUT; otherwise state whether it is an Evil Number."