Мой путь к соревновательному программированию с использованием Javascript (день 2 из 180)

Уровень: легкий

Проблема 3: https://www.codechef.com/problems/FLOW017

«Вам дано целое число N. Напишите программу для вычисления суммы всех цифр числа N ».

Ограничения:

1 ≤ N ≤ 1000000

Пример:

Input:
12345
31203
2123
Output:
15
9
8

Подход и решение:

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

Но вот небольшая проблема: вышеприведенное решение работает только для элементов массива четной длины, но не работает для элементов с нечетным номером один.

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

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

Давайте посмотрим на алгоритм в приведенном ниже коде:

function sumOfDigits(str) {
    const input = str.split('');
    const mid = Math.floor(input.length/2);
    let sum = 0;
    // check if the array length is odd, and add the element to the          sum result
    if (input.length%2 !== 0) {
      sum+= Number(input[mid]);
    }    
    for(let i = 0; i < mid; i++) {
      sum += Number(input[i]) + Number(input[input.length - 1 - i]);
    }
    console.log(Number(sum));
}

Временная сложность:

Давайте сделаем простую математику, чтобы вычислить временную сложность алгоритма, известную как нотация Big O.

Как мы видим, большинство инструкций выполняется за постоянное время O (1), и только один раз нам пришлось пройти через половину элементов массива, что привело к O (n / 2).

В конце, после игнорирования всех констант и рассмотрения только доминирующей, сложность времени выполнения составляет O (n), что является линейным графиком.

Проблема 4: https://www.codechef.com/problems/FLOW017

«Три числа A, B и C - это входные данные. Напишите программу, чтобы найти среди них второе место ».

Ограничения:

1 ≤ A,B,C ≤ 1000000

Пример:

Input:
120 11 400
10213 312 10
10 3 450
Output:
120
312
10

Подход и решение:

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

let largest = -Number.MAX_VALUE;
let secondLargest = -Number.MAX_VALUE;

Затем переберите массив, учитывая два крайних случая:

Если новое значение больше, чем наибольшее значение, тогда наибольшее значение становится вторым по величине, а новое значение становится наибольшим.

secondLargest one = largest one 
largest one  = new value

2. Если новое значение находится между наибольшим и вторым наибольшим значением, т.е. новое значение больше второго наибольшего, но меньше наибольшего. В этом случае текущее второе наибольшее значение потеряет свою позицию, и новое значение примет как второй по величине.

secondLargest one = new value

Давайте посмотрим на реальный алгоритм ниже:

function secondLargest(str) {
    let largest = -Number.MAX_VALUE;
    let secondLargest = -Number.MAX_VALUE;
    const input = str.split(' ');
    const length = input.length;
    for(let i =0; i<length; i++ ) {
        const newValue = Number(input[i]);
        if (newValue > largest) {
            secondLargest = largest;
            largest = newValue
           //[secondLargest, largest] = [largest, newValue]
        } else if (newValue > secondLargest && newValue < largest){
            secondLargest = newValue;
        } 
    }
    if (secondLargest === -Number.MAX_VALUE) {
        console.log('Theres no second largest number');
    } else {
        console.log(Number(secondLargest))
    } 
}

Временная сложность:

На этом все, ребята.

Не стесняйтесь размещать свое лучшее решение в разделе комментариев.

Приветствую и счастливого кодирования!

Мой путь к соревновательному программированию с использованием Javascript (день 2 из 180)

Вопросы по теме