What is optimal way to check all numbers in large array are equal?

Question

Following approaches works on small number of arrays but when I try large volume then it is timing out. What is the best way to check all numbers are equal in large volume of arrays?

In below sample, I am confirming which numbers are uniform between given numbers where it works for small volume (i.e., 1 - 300) but not doing well for large volume (i.e., 1 - 999999999999)

References:

using .every

const uniformInteger = (A, B) => {
  let output = 0;
  for (let i = A; i <= B; i++) {
    const reversed = i.toString().split("").reverse();

    // Option - 1 = using .every
    if (reversed.every((val, i, arr) => val === arr[0])) {
      output++;
    }

  }
  return output;
};

console.log(uniformInteger(1, 300));
// Timed out
// console.log(uniformInteger(1, 999999999999));

using Set

const uniformInteger = (A, B) => {
  let output = 0;
  for (let i = A; i <= B; i++) {
    const reversed = i.toString().split("").reverse();

    // Option - 2 = using Set
    if (new Set(reversed).size == 1) {
      output++;
    }

  }
  return output;
};

console.log(uniformInteger(1, 300));

using another loop to check current and next value

function identical(array) {
  for (var i = 0; i < array.length - 1; i++) {
    if (array[i] !== array[i + 1]) {
      return false;
    }
  }
  return true;
}

const uniformInteger = (A, B) => {
  let output = 0;
  for (let i = A; i <= B; i++) {
    const reversed = i.toString().split("").reverse();

    // Option - 3 = another loop to check current and next value
    if (identical(reversed)) {
      output++;
    }
  }
  return output;
};

console.log(uniformInteger(1, 300));

What exactly is your concept of "all numbers in an array are equal" ? In my understanding this would result in true for `[10, 10, 10]` and false for `[10, 11, 12]` can you give a small example? — derpirscher, Jun 22 '22 at 20:46
Your arrays would never get particularly large - based on your code, the largest array would be 12 elements long (`['9', '9', '9', '9' ...]`). But you're trying to iterate ~1 trillion times, which is probably why you're timing out. Even assuming your entire function runs in `100 ns` per iteration, doing it 1T times would be hours. — wkl, Jun 22 '22 at 20:56
@derpirscher i.e., if the number is 101 then array would be [1,0,1] whereas for 111 it would be [1,1,1]. Here output would increment for 111 because all numbers in array are equal. I am doing loop for all numbers between 1-99999.... where each number will be split up and like my example and performs a check. — GThree, Jun 22 '22 at 21:16
So you are actually checking for all numbers in a certain range if all their digits are equal? — derpirscher, Jun 22 '22 at 21:22
Then have a look at my answer, how to do this efficently. Because if you are looping from 1 to 999999999999 this will take you 3 years, even if each iteration only takes 0.1ms ... — derpirscher, Jun 23 '22 at 14:35

derpirscher · Accepted Answer · 2022-06-24T07:50:50.330

If it's just about counting how many numbers in a certain range have all equal digits, there is no need to inspect billions of numbers which never can fulfill the condition. Optimizing is often not about making the existing approach faster but to check whether there is a better approach for calculating the result.

Because for instance, if you have reached 111111111111 the next number to fulfill your condition will be 222222222222. No need for checking 111111111112, 111111111113, 111111111114 ...

But you can easily calculate the count, because for each "length" of a number (ie 1s, 10s, 100s, 1000s, ....) there are exactly 9 numbers which meet your condition (ie 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222, 333 ...)

Thus for an interval [1, B] where B = 99999.... the count of numbers fulfilling your condition is

ceil(log_10(B)) * 9

Ie for instance, if B == 999 it would be

ceil(log_10(999)) * 9 = ceil(2.99...) * 9 = 3 * 9 = 27
//(ie 1, 2, 3, ..., 9, 11, 22, 33, ..., 99, 111, 222, 333, ..., 999)

If B does not consist of all 9 you have to check if any digit of B is less than the first digit of B or not.

If yes, then the count is

floor(log_10(B)) * 9 + firstDigit - 1

If no, then the count is

floor(log_10(B)) * 9 + firstDigit

Actually, the B = 999.... case can also be handled with these two formulae.

So for instance, if B == 323 the count is

floor(log_10(B)) * 9 + firstDigit - 1 = 2 * 9 + 3 - 1 = 20
//(ie, 1, 2, 3, ..., 9, 11, 22, 33, ..., 99, 111, 222)

If B === 343 then count is

floor(log_10(B)) * 9 + firstDigit = 2 * 9 + 3 = 21
//(ie, 1, 2, 3, ..., 9, 11, 22, 33, ..., 99, 111, 222, 333)

EDIT

If you have an interval [A,B] where A != 1 the final result is of course

count(A,B) = count(1,B) - count(1,A - 1)

I'm not gonna comment on your linked fiddles, because they contain so many errors, I don't even know where to start. So I'm just adding a simple and straight forward implementation

function count(a, b) {
  if (a > b || a < 1 || b < 1)
    return 0;
    
  if (a > 1)
    return  count(1, b) - count(1, a - 1);
  
  let 
    result = 9 * Math.floor(Math.log10(b)),
    smallest = 9,
    first = 0

  while (b > 0) {
    smallest = Math.min(smallest, b % 10)
    first = b;
    b = Math.floor(b / 10)
  }
  
  result += first;
  if (smallest < first) result -= 1;
  return result;
}


let testinvervals = [
  [1,1],
  [1, 10],
  [1, 1000],
  [1, 1234],
  [1, 4321],
  [2, 9],
  [2, 10],
  [2, 11],
  [11, 99],
  [12, 99],
  [11, 22],
  [33, 33]
]

for (let tv of testinvervals) {
    console.log(`[${tv[0]} , ${tv[1]}]`, "-->", count(tv[0], tv[1]))
}

if I understood your approach correctly, are you suggesting this way https://jsfiddle.net/9m68yo5u/ ? If yes, I guess this works when my first value is 1 but not if I want to make it static. Looks like I am missing something. — GThree, Jun 23 '22 at 15:46
I changed the range then I see incorrect result https://jsfiddle.net/c7pah1zw/, I get incorrect result. What am I missing here? — GThree, Jun 23 '22 at 20:26

What is optimal way to check all numbers in large array are equal?

1 Answers1