Генерация чисел в последовательности Порядок

Question

Я хочу создать искомое значение по позиции, указанной в чеке. Например, если введено 20, функция должна генерировать числа, начиная с 0, и продолжать в порядке возрастания до создания 20 цифр, а затем вывести значение 20-го числа git в сгенерированной строке чисел (01234567891011121314), которое равно 4 Я попробовал это ниже, однако это неэффективно, когда дело доходит до цифр, таких как 1 000 000 000,

[...Array(5).keys()];  output => [0, 1, 2, 3, 4]

Отредактируйте этот пост, чтобы уточнить, что я пытаюсь найти более эффективное решение. Здесь я пытаюсь получить ответ для длинных чисел (1 000 000 000) менее чем за одну секунду.

У меня уже есть решение, но оно занимает более 1 секунды.

 [...Array(5).keys()].join("")[4]; output => 4

Answer 1

Вот простой подход без использования массивов.

let N = 1000000000, digitsCount = 0, currentNumber = 0;
console.time('Took time: ');
const digits = (x)=>{
    if(x<10)
        return 1;
    if(x<100)
        return 2;
    if(x<1000)
        return 3;
    if(x<10000)
        return 4;
    if(x<100000)
        return 5;
    if(x<1000000)
        return 6;
    if(x<10000000)
        return 7;
    if(x<100000000)
        return 8;
    if(x<1000000000)
        return 9;
    return 10; // Default
}
while(true){
    digitsCount += digits(currentNumber);
    if(digitsCount >= N)
        break;
    currentNumber++;
}
console.timeEnd('Took time: ');
console.log(String(currentNumber)[N-digitsCount+digits(currentNumber)-1])

---

Вывод (Время выполнения может отличаться для вас, но оно будет меньше 1 секунды (или 1000 мс).)

Took time: : 487.860ms
9

Answer 2

Это почти идентично постоянной Champernowne .

. Решение от math.stackexchange :

(переполнение стека, к сожалению, не поддерживает MathJax)

Первый шаг - определить, в каком десятилетии вы находитесь. Из 1 цифры * 9 цифр git чисел, 2⋅90 = 180 цифр из чисел 2 di git, всего 189, и обычно n⋅9⋅10n − 1 из чисел n di git. Найдя десятилетие, вы можете вычесть цифры из предыдущих десятилетий. Итак, если вы хотите 765-е число git, первые 189 появятся в первом и втором десятилетиях, поэтому мы хотим получить 576-е число git из 3-х чисел git. Это прибудет в ⌉5763⌉ = 192-е число, которое составляет 291. Как 576≡3 (mod3), di git равно 1

Программно:

const getDigit = (target) => {
  let i = 0;
  let xDigitNumbers = 1; // eg 1 digit numbers, 2 digit numbers
  let digitsSoFar = 1;
  while (true) {
    const digitsThisDecade = xDigitNumbers * 9 * 10 ** (xDigitNumbers - 1);
    if (digitsSoFar + digitsThisDecade > target) {
      // Then this is the "decade" in which the target digit is
      
      // digitIndexThisDecade: eg, starting from '100101102', to find the last '1' in '101', digitIndexThisDecade will be 6
      const digitIndexThisDecade = target - digitsSoFar;
      // numIndexThisDecade: this identifies the index of the number in the decade
      // eg, starting from '100101102', this could be index 2 to correspond to 101 (one-indexed)
      const numIndexThisDecade = Math.floor(digitIndexThisDecade / xDigitNumbers);
      // decadeStartNum: the number right before the decade starts (0, 9, 99, 999)
      const decadeStartNum = 10 ** (xDigitNumbers - 1);
      // num: the number in which the target index lies, eg 101
      const num = decadeStartNum + numIndexThisDecade;
      // digitIndexInNum: the digit index in num that the target is
      // eg, for 101, targeting the last '1' will come from a digitIndexInNum of 2 (zero-indexed)
      const digitIndexInNum = digitIndexThisDecade % xDigitNumbers;
      return String(num)[digitIndexInNum]
    }
    digitsSoFar += digitsThisDecade;
    xDigitNumbers++;
  }
};



for (let i = 0; i < 1000; i++) {
  document.write(`${i}: ${getDigit(i)}<br>`);
}

Answer 3

Я использовал .join(""), чтобы преобразовать массив в строку '01234567891011121314151617181920'

, а затем получить доступ к N-му числу с помощью строки индексации

N=20;
console.log ( [...Array(N+1).keys()].join("")[N-1] )     //OUTPUT 4

РЕДАКТИРОВАТЬ: я думаю, что это решение, которое вам вообще не нужно создавать массив ... его математическая формула

Blockquote

Answer 4

В моем решении нам не нужны большие итерации и циклы ... Но это решение большое для простого понимания ...

Я сделал это до 6 цифр, и это очень эффективно .. .и могут быть сделаны для любого количества цифр ... И даже могут быть уменьшены до небольших функций, но это будет слишком сложно понять ...

Итак, общее количество для данных цифр: для 1-го разряда git Числа, они 10 (от 0 до 9) ....

Для 2 Di git чисел, они 9 * 10 => 90, и всего цифры ==> 90 * 2 = => 180 ...

Для 3-х git чисел, 9 * 10 * 10 => 900 и общих цифр ==> 90 * 3 ==> 2700 ...

Для 4 Di git чисел, 9 * 10 * 10 * 10 => 9000 и общих цифр ==> 9000 * 4 ==> 36000 ...

Функция для получения общих цифр для заданный (Количество цифр)

let totalDigits = n => {
    if (n == 1) return 10;
    return 9 * (10 ** (n - 1)) * n;
}

Теперь мы устанавливаем диапазон позиции для разных цифр, для 1 Di git, это между 1 и 10 ....

для 2 цифр это между 11 (1 + 10) и 190 (180 + 10) ... (позиция 1 в 10 11, а второе 9 из 99 - 190) ...

для 3 цифр, это между 191 (1 + 10 + 180) и 2890 (2700 + 180 + 10) ... И так далее

для n Di git, функция для получения диапазона равна

//  This function is used to find Range for Positions... Eg : 2 digit Numbers are upto Position 190...(Position 191 is "100" first digit => 1 ) 
let digitN = n => {
    if (n == 1) return totalDigits(1);
    return digitN(n - 1) + totalDigits(n);
}

// To Finally set Ranege for a Given Digit Number... for 1 its [1,10] , for 2 its [11,190]
let positionRange = n => {
    if (n == 1) return [1, 10];
    else return [digitN(n - 1), digitN(n)]
}

Таким образом, окончательное решение составляет

//  This Function tells the total number of digits for the given digit... Eg : there are 10 one digit Numbers , 180 Two Digit Numbers , 2700 3 Digit Numbers
let totalDigits = n => {
    if (n == 1) return 10;
    return 9 * (10 ** (n - 1)) * n;
}

//  This function is used to find Range for Positions... Eg : 2 digit Numbers are upto Position 190...(Position 191 is "100" first digit => 1 ) 
let digitN = n => {
    if (n == 1) return totalDigits(1);
    return digitN(n - 1) + totalDigits(n);
}

// To Finally set Ranege for a Given Digit Number... for 1 its [1,10] , for 2 its [11,190]
let positionRange = n => {
    if (n == 1) return [1, 10];
    else return [digitN(n - 1), digitN(n)]
}

// A simple Hack to get same value for Different Consecutive Numbers , (0.3 or 0.6 or 0.9 or 1 return 1) 
let getDigit = n => {
    if (dataType(n) == "float") {
        n = Math.floor(n);
        n++;
    }
    return n;
}
// To check for Float or Integer Values
function dataType(x) {
    if (Math.round(x) === x) {
        return 'integer';
    }
    return 'float';
}

function f(position) {

    let result, charInd, temp;

    if ((position >= positionRange(1)[0]) && (position <= positionRange(1)[1])) {      //   Positions   1 to 10  (1 Digit Numbers)
        result = position - 1;
        charInd = 0
    }
    if ((position > positionRange(2)[0]) && (position <= positionRange(2)[1])) {      //   Positions   11 to 190 (2 Digit Numbers)
        temp = (position - 10) / 2;
        temp = getDigit(temp);
        result = temp + 9;
        charInd = (position - 11) % 2
    }
    if ((position > positionRange(3)[0]) && (position <= positionRange(3)[1])) {      //   Positions   191 to 2890 (3 Digit Numbers)
        temp = (position - 190) / 3;
        temp = getDigit(temp);
        result = temp + 99;
        charInd = (position - 191) % 3
    }
    if ((position > positionRange(4)[0]) && (position <= positionRange(4)[1])) {      //   Positions   2891 to 38890 (4 Digit Numbers)
        temp = (position - 2890) / 4;
        temp = getDigit(temp);
        result = temp + 999;
        charInd = (position - 2891) % 4
    }
    if ((position > positionRange(5)[0]) && (position <= positionRange(5)[1])) {      //    Positions  38890 to 488890 (5 Digit Numbers)
        temp = (position - 38890) / 5;
        temp = getDigit(temp);
        result = temp + 9999;
        charInd = (position - 38891) % 5
    }
    if ((position > positionRange(6)[0]) && (position <= positionRange(6)[1])) {      //   Positions  488890 to 5888890 (6 Digit Numbers)
        temp = (position - 488890) / 6 ;
        temp = getDigit(temp);
        result = temp + 99999;
        charInd = (position - 488891) % 6
    }
    finalChar = String(result)[charInd];

    console.log("Given Position => ", position, "  Result Number => ", result, "Char Index ==> ", charInd, "Final Char => ", finalChar);
}
let d1 = Date.now();
f(138971); //  Given Position =>  138971   Result Number =>  30016 Char Index ==>  0 Final Char =>  3
let d2 = Date.now();

console.log(d2-d1) ;      //  351