Generate and Sort Lottery Numbers in C++

This is a fairly trivial problem, but I remember being struck at how the most obvious solution sometimes isn’t the best. It’s often worth thinking a little more into a problem, and not just blindly start coding the first solution you came across.

My university course comprised three years of study and one year of industry placement, conveniently sandwiched between years two and three.

Around Easter-time I responded to an advertisement in the local paper for a local company called Head Software International, whoHead Software International were looking to recruit ‘Junior Programmers.’ I responded in the vague hope that they would consider hiring an undergraduate for the position for one-year only.

Soon after this I got a response, and was invited for an interview. I don’t remember much about it, except I was asked to write some code (something every interviewee for a programming job should be required to do).

I do, however, remember one of the questions very well:

Write a program that generates a line of National Lottery number.

Bonus: Sort the numbers into order.

At the time, the British National Lottery had only one game. You picked six different numbers between 1 and 49, and you won varying amounts depending on how many came up in the draw.

“Easy-peasy,” I thought. So I promptly set about writing a program with the following features:

  1. Declare array of six integers.
  2. Loop through the array generating a random number for each element, and checking it against all the previous entries.
  3. Sort the array.

So, excusing variable declarations, your program in C++ (yes, C++) might look something like:

while (i<6)
{
    num = (rand() % 49) + 1;

    //check our number doesn't already exist
    for (j = 0; j < i; j++)
    {
        bExists = (lotteryNumbers[j] == num);
    }

    //add to the array
    if (!bExists)
    {
        lotteryNumbers[i] = num;
        i++;
    }
}

//now sort the array....

Although I did include an Insertion Sort algorithm, you’ll forgive me for not including it here. I was even tenacious enough to suggest using some of the in-built sorting capabilities within C++.

This all received a positive response. One of the interviewers commented – ‘No-one has ever coded Bubble Sort as part of that solution.’ (It was an Insertion Sort, but I still preened).

Anyhow, I got the job. Sometime later, a developer at the company explained to me a different approach  (which apparently no-one had ever come up with in the interview). This is what they suggested:

  1. Declare an array of 49 booleans.
  2. Initialise each element to false.
  3. Generate your random number (lets call it x)
  4. Check array[x] - Set it to true if false, and increment our counter.
  5. Repeat 3-4 until our counter is six.

So it might look something like:

bool lotteryNumbers[49];

for (i=0; i<49; i++)
{
    lotteryNumbers[i] = false;
}

while (j<6)
{
    num = (rand() % 49) + 1;
    if (!lotteryNumbers[num])
    {
        lotteryNumbers[num] = true;
        j++;
    }
}

The advantages of this are as follows:

  1. You remove the need to loop through all your existing array items to check for a number’s existence.
  2. You don’t have to sort, as it is presorted!

You do have the disadvantage in that every time you want to access the numbers you must loop through (up to) 49 array items. To solve this you can do a one-time transfer to a six-element byte array after the generation is complete.

One thought on “Generate and Sort Lottery Numbers in C++

  1. Pingback: Of Spam and Post Content… | James Wiseman

Leave a Reply