ISC Practicals and Theory - Evil Numbers in a Range

An Evil Number is a positive whole number that has an even number of 1s in its binary (base-2) form. This version accepts a range m to n and prints every Evil Number in it, followed by how many there are.

Definition

A positive integer $N$ is an Evil Number if the count of 1s in its binary equivalent is even. For example, $6 = 110_2$ has two 1s, so 6 is Evil. $7 = 111_2$ has three 1s, so 7 is not Evil (it is an Odious Number). Between 1 and 20 the Evil Numbers are 3, 5, 6, 9, 10, 12, 15, 17, 18 and 20.

Algorithm

1. accept() reads the two ends of the range into m and n.
2. In main, if m <= 0, n <= 0 or m > n, print INVALID INPUT and stop.
3. Otherwise showEvil() sets total = 0 and runs a loop with i from m to n:
   • Call isEvil(i). It counts the 1s in the binary form of i by repeated division by 2: while x > 0, add 1 to ones if x % 2 == 1, then x = x / 2. It returns true when ones is even.
   • If it returns true, print i followed by a space and add 1 to total.
4. After the loop, print a new line and then the frequency, total.

Program

accept() reads the range, isEvil() decides for one number, and showEvil() goes through the range, printing and counting.

import java.util.Scanner;

public class EvilRange
{
    int m;          // the start of the range
    int n;          // the end of the range
    int total;      // how many Evil Numbers were found in the range

    // Step 1: read both ends of the range
    public void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter m: ");
        m = sc.nextInt();
        System.out.print("Enter n: ");
        n = sc.nextInt();
    }

    // Decides whether one number is Evil. Each remainder (x % 2) is the next
    // binary digit, so we count the remainders that are 1 and check that
    // the count is even.
    public boolean isEvil(int x)
    {
        int ones = 0;
        while (x > 0)
        {
            if (x % 2 == 1)    // this binary digit is a 1
                ones++;
            x = x / 2;         // drop that digit and move to the next one
        }
        return ones % 2 == 0;
    }

    // Print every Evil Number from m to n on one line and count them
    public void showEvil()
    {
        total = 0;
        System.out.println("Evil Numbers from " + m + " to " + n + ":");
        for (int i = m; i <= n; i++)
        {
            if (isEvil(i))
            {
                System.out.print(i + " ");
                total++;
            }
        }
        System.out.println();
        System.out.println("Frequency of Evil Numbers = " + total);
    }

    public static void main(String args[])
    {
        EvilRange ob = new EvilRange();
        ob.accept();
        if (ob.m <= 0 || ob.n <= 0 || ob.m > ob.n)
            System.out.println("INVALID INPUT");
        else
            ob.showEvil();
    }
}

Variable description table

Sample input and output

Enter m: 1
Enter n: 20
Evil Numbers from 1 to 20:
3 5 6 9 10 12 15 17 18 20 
Frequency of Evil Numbers = 10

Enter m: 5
Enter n: 8
Evil Numbers from 5 to 8:
5 6 
Frequency of Evil Numbers = 2

Enter m: 7
Enter n: 8
Evil Numbers from 7 to 8:

Frequency of Evil Numbers = 0

Enter m: 20
Enter n: 10
INVALID INPUT

Dry run

Input: m = 5, n = 8

For i = 5, isEvil(5) works as follows:

The loop ends (x = 0) and ones = 2 is even, so it returns true. After the loop ends at i = 9, the program prints Frequency of Evil Numbers = 2.

For m = 20, n = 10 the check in main finds m > n, so showEvil() is never called and INVALID INPUT is printed.

Variations

1. Odious Numbers in a range: "Accept two numbers m and n and print all Odious Numbers between them, that is, numbers with an odd number of 1s in binary."
2. Both classifications: "Accept a range and print the Evil Numbers and the Odious Numbers in it separately, with the frequency of each."
3. Binary equivalent: "Accept a range and print each Evil Number in it together with its binary equivalent."