# Most Efficient Method To Check For Range Of Numbers Within Number Without Duplicates

## 28 December 2015 - 1 answer

Given a number `n` , a minimum number `min` , a maximum number `max` , what is the most efficient method to determine

1. Number `n` is or is not within range , inclusive of , `min` - `max`

2. Number `n` does or does not contain duplicate numbers

3. Efficiency meaning here that the method or set of methods requires the least amount of computational resources and returns either `true` or `false` in the least amount of time

4. Context: Condition at `if` within a `for` loop which could require from thousands to hundreds of thousands of iterations to return a result; where milliseconds required to return `true` or `false` as to `Number` check could affect performance

At `Profiles` panel at `DevTools` on a collection of `71,3307` items iterated, `RegExp` below was listed as using `27.2ms` of total `1097.3ms` to complete loop . At a collection of `836,7628` items iterated `RegExp` below used `193.5ms` within total of `11285.3ms` .

Requirement: Most efficient method to return `Boolean``true` or `false` given above parameters , within the least amount of time.

Note: Solution does not have to be limited to `RegExp` ; used below as the pattern returned expected results.

Current `js` utilizing `RegExp``re` , `RegExp.protype.test()`

``````var min = 2
, max = 7
, re = new RegExp("[" + min + "-" + max + "](.)(?!=\1)", "g")
, arr = [81, 35, 22, 45, 49];

for (var i = 0; i < arr.length; i++) {
console.log(re.test(arr[i]), i, arr[i])
/*
false 0 81
true 1 35
false 2 22
true 3 45
false 4 49
*/
}``````

# Associative arrays approach:

This has the advantage of being easily understandable.

``````function checkDigits(min, max, n) {
var digits = Array(10);                   // Declare the length of the array (the 10 digits) to avoid any further memory allocation
while (n) {
d = (n % 10);                         // Get last digit
n = n / 10 >>0;                       // Remove it from our number (the >>0 bit is equivalent to compose(Math.floor, Math.abs))
if (d < min || d > max || digits[d])  // Test if "d" is outside the range or if it has been checked in the "digits" array
return false;
else
digits[d] = true;                 // Mark the digit as existing
}
}
``````

``````var min = 2
, max = 7
, arr = [81, 35, 22, 45, 49];

function checkDigits(min, max, n) {
var digits = Array(10);                   // Declare the length of the array (the 10 digits) to avoid any further memory allocation
while (n) {
d = (n % 10);                         // Get last digit
n = n / 10 >>0;                       // Remove it from our number (the >>0 bit is equivalent to compose(Math.floor, Math.abs))
if (d < min || d > max || digits[d])  // Test if "d" is outside the range or if it has been checked in the "digits" array
return false;
else
digits[d] = true;                 // Mark the digit as existing
}
return true;
}

for (var i = 0; i <

for (var i = 0; i < arr.length; i++) {
console.log(checkDigits(min, max, arr[i]), i, arr[i])
}``````

# Binary mask approach:

This replaces the Array with an integer that is in effect used as an array of bits. It should be faster.

``````function checkDigits(min, max, n) {
var digits = 0;
while (n) {
d = (n % 10);
n = n / 10 >>0;
if (d < min || d > max || (digits & (1 << d)))
return false;
else
digits |= 1 << d;
}
return true;
}
``````

``````function checkDigits(min, max, n) {
var digits = 0;
while (n) {
d = (n % 10);
n = n / 10 >>0;
if (d < min || d > max || (digits & (1 << d)))
return false;
else
digits |= 1 << d;
}
return true;
}``````

### Explanation for binary mask approach:

`1 << d` creates a bit mask, an integer with the `d` bit set and all other bits set to 0.
`digits |= 1 << d` sets the bit marked by our bit mask on the integer `digits`.
`digits & (1 << d)` compares the bit marked by our bit mask with `digits`, the collection of previously marked bits.
See the docs on bitwise operators if you want to understand this in detail.

So, if we were to check 626, our numbers would go like this:

``````________n_____626_______________
|
d  |  6
digits  |  0000000000
|
________n_____62________________
|
d  |  2