Perl Weekly Challenge 130: Odd Number

by Abigail

Challenge

You are given an array of positive integers, such that all the numbers appear even number of times except one number.

Write a script to find that integer.

Example 1

Input: @N = (2, 5, 4, 4, 5, 5, 2)
Output: 5

5 appears 3 times in the array where as all other numbers 2 and 4 appears exactly twice.

Example 2

Input: @N = (1, 2, 3, 4, 3, 2, 1, 4, 4)
Output: 4

Solution

This challenge is pretty straight forward. For languages with a hash (or map, or dictionary, etc), we extract the positive numbers from the input, and count them using the hash. We then find the element in the hash for which its count is odd. For languages lacking such a construct, we also extract the positive integers from the input, and we sort those. We then look at each pair of numbers, and look for a mismatch. If there is a mismatch, the first number of the pair is the odd one out. If all pairs match, the last number is the odd one out (there will be an odd number of numbers).

We will read the data from standard input. Each line of input is a different array — so we print a number for each line of input. We assume the numbers are separated by spaces (required for our solutions in AWK, Bash and C; for the other languages, the numbers may be separated by anything non-numeric).

Perl

Extract the numbers from the input, and count them:

my %numbers;
$numbers {$_} ++ for /[1-9][0-9]*/g;

Find the one number which occurs an odd number of times, and print it:

say grep {$numbers {$_} % 2} keys %numbers;

Find the full program on GitHub.

C

Read a line of input, and first count the number of positive integers it contains:

char *  line    = NULL;
size_t  len     = 0;
size_t  str_len;
while ((str_len = getline (&line, &len, stdin)) != -1) {
    char * line_ptr = line;
    int offset = 0;
    int count  = 0;
    int number;
    while (sscanf (line_ptr, "%d%n", &number, &offset) == 1) {
        count ++;
        line_ptr += offset;
    }

Given the number of integers, we can allocate an array, and put the numbers into an array:

int * numbers;
if ((numbers = (int *) malloc (count * sizeof (int))) == NULL) {
    perror ("Malloc failed");
    exit (1);
}
line_ptr = line;
count = 0;
while (sscanf (line_ptr, "%d%n", &numbers [count], &offset) == 1) {
    count ++;
    line_ptr += offset;
}

We can now sort them, using the buildin qsort. qsort needs a helper function, which compares two elements, indicating which one is the smaller (or whether they are equal).

int cmp (const void * a, const void * b) {
    return (* (int *) a - * (int *) b);
}

qsort (numbers, count, sizeof (int), cmp);

We can now find the number which is the odd one out:

int found = 0;
for (int i = 0; i < count - 1; i += 2) {
    if (numbers [i] != numbers [i + 1]) {
        printf ("%d\n", numbers [i]);
        found ++;
    }
}
if (!found) { /* Must be last element */
    printf ("%d\n", numbers [count - 1]);
}

Find the full program on GitHub.

Other languages

We also have solutions in AWK, Bash, Lua, Node.js, Python, and Ruby. All of them are similar to the Perl solution.


Please leave any comments as a GitHub issue.