Поиск максимальных разрядов между заданным диапазоном

Question

Два числа (a, b) считаются похожими, если < = 10 * b и b < = 10 * a. Теперь, учитывая два диапазона низких и высоких значений, возвращаем коллекцию, содержащую максимальное количество не похожих чисел между заданным диапазоном.

Я могу только думать о приближении грубой силы. Просто нужно знать, как решить эту проблему с лучшей сложностью.

Answer 1

Из вашего описания я вижу, что два числа аналогичны, если более крупный из них не более чем в 10 раз больше, чем маленький. Поэтому, если вы хотите найти максимальный набор чисел из диапазона [low ... high], чтобы никакие два числа в этом наборе не были похожи, решение должно начинаться с наименьшего числа в диапазоне, то есть от «низкого», и каждый раз берем следующее наименьшее число, которое не похоже на какое-либо число в наборе (или его же, если вы просто проверяете, не похоже ли это на элемент max в наборе).

алгоритм:

принять низкий, то 10 * низкий + 1, 10 * (10 * низкий + 1) + 1 и т.д ... до тех пор, пока не превысит высокий предел.

Answer 2

Если я правильно понял проблему правильно, это должно работать:

// start with smallest number: 

var numbers = []; 
var number = range.lowest; 
// while not reached end of range 
while (number <= range.highest) { 
    // add this number; 
    numbers.push(number); 
    // find next not similar number 
    number = numbers * 10 + 1; 
} 

// start with highest number: 

var numbers = []; 
var number = range.highest; 
// while not reached end of range 
while (number >= range.lowest) { 
    numbers.push(number); 
    // find next non-similar number 
    var newNumber = Math.floor(number/10.0); 
    if (numNumber == number/10.0); 
     newNumber--; 
    number = newNumber; 
} 

Последний подход мог бы, возможно, найти больше чисел, чем первый, попробуйте. Однако, вероятно, всегда будут разные наборы не похожих чисел с равным размером.