## Objective

Create a function to pick a random integer from a given arithmetic sequence.

## Description

In the previous exercise, Sequence In Range, we defined a function `printSequence()`

to print a sequence that starts at a given integer `a`

, proceeds with a common difference `d`

, and ends before an integer `b`

(exclusive).

If you've not attempted to solve the exercise, it's recommended that you do so because this exercise follows from it.

Let's say that `a = 1`

, `b = 10`

, and `d = 1`

. This gives us the following sequence:

1, 2, 3, 4, 5, 6, 7, 8, 9

If we want to randomly pick one integer from this sequence, what could it be? Well, since it's random, it could be anything. *1?* Why not. *2?* Probably. *9?* Probably. *5?* You get it.

**In this exercise, you have to create a function randomPick() which has the same parameters as printSequence(), just that it doesn't print anything but instead returns a random integer from the underlying sequence.**

For example, calling `randomPick(1, 10, 1)`

would return any integer between `1`

and `10`

(exclusive). Similarly, `randomPick(10, 100, 25)`

would return any integer from the sequence 10, 35, 60, and 85.

As before, if the parameters are such that there's no existing sequence (which we discussed in the Sequence In Range exercise), the function should treat this case specially. In particular, the function should return `null`

(to signify that there's simply nothing to randomly pick).

Here are a couple of usages of `randomPick()`

:

`randomPick(1, 10, 1)`

`5`

`randomPick(1, 10, 1)`

`9`

`randomPick(1, 10, 1)`

`1`

`randomPick(10, 100, 25)`

`10`

`randomPick(10, 100, 25)`

`85`

`randomPick(10, 10, 25)`

`null`

`randomPick(1, 10, -1)`

`null`

In the second-last statement, since the first two arguments (corresponding to a and b) are the same, the function returns `null`

as there's no sequence to consider.

Similarly, in the last statement, since the first two arguments represent an increasing sequence (starting at a smaller value and ending at a larger one), the `d`

parameter must be positive. However, since it's negative, `null`

is returned.

## New file

Inside the directory you created for this course on JavaScript, create a new folder called **Exercise-12-Random-Picks** and put the .html solution files for this exercise within it.

## Solution

The simplest solution to this exercise would be to augment the definition of `printSequence()`

from the Sequence In Range exercise.

Here's the `printSequence()`

function:

```
function printSequence(a, b, d) {
if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
document.write('Nothing to print');
return;
}
for (var x = a; Math.sign(d) * (x - b) < 0; x += d) {
var sep = ', ';
if (x === a) {
sep = '';
}
document.write(sep + x);
}
}
```

In order to return a random integer from the underlying sequence, we just ought to address two cases:

- Return
`null`

when the parameters represent an empty/non-existing sequence. - Return a random element from the constructed list of numbers.

The first case is trivial — return `null`

from the `if`

conditional.

Let's accomplish this right after defining the function `randomPick()`

:

```
function randomPick(a, b, d) {
if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
return null;
}
}
```

Now, we're only left with the second case, i.e. to return a random element from the constructed list of numbers. This is easy as well.

In `printSequence()`

, we right away print the current item of the sequence. In `randomPick()`

, however, we ought to push it to an array — let's call it ** nums** — and then compute a random integer between

`0`

and *n*

(exclusive), where *is the length of*

`n`

`nums`

.This random integer acts as the index of the element of `nums`

to return.

Let's implement this now:

```
function randomPick(a, b, d) {
if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
return null;
}
var nums = [];
for (var x = a; Math.sign(d) * (x - b) < 0; x += d) {
nums.push(x);
}
var randomIndex = Math.floor(Math.random() * nums.length);
return nums[randomIndex];
}
```

The ** randomIndex** variable defined here stores a randomly-generated integer, as we discussed above, acting as the index of an element of

`nums`

to return. And in the end, this is exactly what's done in line 10.Let's now test this function on a couple of values:

`randomPick(1, 10, 1)`

`5`

`randomPick(1, 10, 1)`

`9`

`randomPick(1, 10, 1)`

`1`

`randomPick(10, 100, 25)`

`10`

`randomPick(10, 100, 25)`

`85`

`randomPick(10, 10, 25)`

`null`

`randomPick(1, 10, -1)`

`null`

And this completes the exercise.

But one question remains to be answered: *Is this implementation of randomPick() OK?*

## An efficient solution

No doubt in that the function above always returns back an integer from the underlying sequence (represented by the given parameters); it never makes up values on its own.

However, gaze at the function for a second or two. *Does it seem sensible to take the approach that we're taking right now?*

In other words, is it wise enough to create a whole list modeling the sequence and only *then* extract a random element from it? *Should we really be doing so?*

Well, as it turns out, there is a quick mathematical trick, following from the theory of arithmetic sequences, that we can leverage in implementing `randomPick()`

**without generating a list of numbers** whatsoever.

*Yes, that's right!* We can ditch the list completely. Pure math will instead take over and return a random integer from the sequence represented by the three given parameters of `randomPick()`

.

Let's appreciate this mathematical trick.

The general form of an arithmetic sequence's ::i^{th}:: term is as follows:

where ::a:: is the initial term and ::d:: is the common difference.

In `randomPick()`

, we are given the maximum integer ::b:: right before which the sequence should end. The formula above and this integer ::b:: are of particular importance.

That is, we use the formula and ::b:: to determine the largest possible value of ::i:: for the sequence, where ::i:: is known to start at ::0::.

In `randomPick()`

, we can then compute a random number between ::0:: and this value of ::i:: (exclusive) and then plug in the ::i:: into the formula above to obtain the corresponding element ::A(i):: of the sequence.

Let's see how to compute this maximum ::i:::

The expression inside the ceil function is obtained by rearranging the formula given above for ::A(i)::. The ceil function is used because ::i:: should be an integer, and it can't be the lesser integer since we need to exclude any value that is equal to ::b::.

Let's accomplish this in `randomPick()`

:

```
function randomPick(a, b, d) {
if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
return null;
}
var randomIndex = Math.floor(Math.random() * Math.ceil((b - a) / d));
return a + d * randomIndex;
}
```

The `Math.ceil()`

expression is the same as the equation given above. As before, `randomIndex`

represents a random integer denoting the index of an element of the underlying sequence to return.

This element is then computed using `randomIndex`

and the arithmetic sequence's ::i^{th}:: term formula: `a + d * randomIndex`

.

And there you have it; an extremely efficient implementation of `randomPick()`

.

See how the list has gone away completely. Now when we call `randomPick()`

with a given set of arguments, there's no memory consumed in generating a list to represent the sequence.

Besides memory, the implementation is even more swift is terms of run time. There is no `for`

loop and no list to iterate over — the random element is picked, more or less, in constant time, by some simple yet beautiful mathematics.