Показать сообщение отдельно
  #2 (permalink)  
Старый 25.05.2021, 13:59
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,005

Вариант, работающий за линейное время

function waysToMakeFair(arr) {
  if (!arr || !arr.length) {
    return 0;
  }
  let fullDelta = 0;
  const deltas = new Array(arr.length);
  for (let i = 0; i < arr.length; ++i) {
    fullDelta += i % 2 ? -arr[i] : arr[i];
    deltas[i] = fullDelta;
  }
  let count = 0;
  for (let i = 0; i < arr.length; ++i) {
    const prevDelta = i > 0 ? deltas[i - 1] : 0
    const nextDelta = fullDelta - deltas[i]
    if (prevDelta - nextDelta === 0) {
      count++
    }
  }
  return count
}

alert(waysToMakeFair([2,1,6,4]));
Ответить с цитированием