Notes

Java Passing Cars

public class Solution {
    public static int passingCars(int[] a) {
        long passingCars = 0;
        int multiply = 0;

        for (int i : a) {
            if (i == 0) {
                multiply++;
            } else if (multiply > 0) {
                passingCars += multiply;
                if (passingCars > 1000000000) {
                    return -1;
                }
            }
        }

        return (int) passingCars;
    }
}

This counts eastbound cars as it scans, then adds them whenever a westbound car appears.

Lisp Passing Cars

(defun passing-cars (a)
  (let ((passing-cars 0)
        (multiply 0))
    (dolist (i a)
      (if (zerop i)
          (incf multiply)
          (when (> multiply 0)
            (incf passing-cars multiply)
            (when (> passing-cars 1000000000)
              (return-from passing-cars -1)))))
    passing-cars))

This counts eastbound cars as it scans, then adds them whenever a westbound car appears.

PHP Passing Cars

function passingCars(array $a): int
{
    $passingCars = $multiply = 0;
    foreach ($a as $i) {
        if ($i === 0) {
            $multiply++;
        } elseif ($multiply > 0) {
            $passingCars += $multiply;
            if ($passingCars > 1000000000) {
                return -1;
            }
        }
    }

    return $passingCars;
}

This counts eastbound cars as it scans, then adds them whenever a westbound car appears.

Python Passing Cars

def passing_cars(a: list[int]) -> int:
    passing = 0
    multiply = 0
    for i in a:
        if i == 0:
            multiply += 1
        elif multiply > 0:
            passing += multiply
            if passing > 1000000000:
                return -1

    return passing

This counts eastbound cars as it scans, then adds them whenever a westbound car appears.

Rust Passing Cars

fn passing_cars(a: &[i64]) -> i64 {
    let mut passing_cars = 0i64;
    let mut multiply = 0i64;
    for &i in a {
        if i == 0 {
            multiply += 1;
        } else if multiply > 0 {
            passing_cars += multiply;
            if passing_cars > 1_000_000_000 {
                return -1;
            }
        }
    }

    passing_cars
}

This counts eastbound cars as it scans, then adds them whenever a westbound car appears.

TypeScript Passing Cars

function passingCars(a: number[]): number {
  let passingCars = 0;
  let multiply = 0;

  for (const i of a) {
    if (i === 0) {
      multiply++;
    } else if (multiply > 0) {
      passingCars += multiply;
      if (passingCars > 1000000000) {
        return -1;
      }
    }
  }

  return passingCars;
}

This counts eastbound cars as it scans, then adds them whenever a westbound car appears.

Bash Peaks

peaks() {
    local -n _arr="$1"
    local _n=${#_arr[@]}
    if (( _n <= 2 )); then
        echo 0
        return
    fi
    local -a _sum
    for ((_i = 0; _i < _n; _i++)); do _sum[_i]=0; done
    local _last=-1 _dist=0 _i
    for ((_i = 1; _i + 1 < _n; _i++)); do
        _sum[_i]=${_sum[_i-1]}
        if (( _arr[_i] > _arr[_i-1] && _arr[_i] > _arr[_i+1] )); then
            if (( _i - _last > _dist )); then _dist=$(( _i - _last )); fi
            _last=$_i
            (( _sum[_i]++ ))
        fi
    done
    _sum[_n-1]=${_sum[_n-2]}
    if (( _sum[_n-1] == 0 )); then
        echo 0
        return
    fi
    if (( _n - _last > _dist )); then _dist=$(( _n - _last )); fi
    local _j
    for ((_i = (_dist >> 1) + 1; _i < _dist; _i++)); do
        if (( _n % _i == 0 )); then
            _last=0
            for ((_j = _i; _j <= _n; _j += _i)); do
                if (( _sum[_j-1] <= _last )); then
                    break
                fi
                _last=${_sum[_j-1]}
            done
            if (( _j > _n )); then
                echo $(( _n / _i ))
                return
            fi
        fi
    done
    for ((_last = _dist; _n % _last != 0; )); do
        ((_last++))
    done
    echo $(( _n / _last ))
}

This finds the peak positions, then tests how many equal blocks can each contain at least one peak.

C++ Peaks

#include <algorithm>
#include <vector>

int peaks(const std::vector<int>& a)
{
    int n = static_cast<int>(a.size());
    if (n <= 2) {
        return 0;
    }

    std::vector<int> sum(n, 0);
    int last = -1;
    int dist = 0;

    for (int i = 1; i + 1 < n; ++i) {
        sum[i] = sum[i - 1];
        if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
            dist = std::max(dist, i - last);
            last = i;
            ++sum[i];
        }
    }

    sum[n - 1] = sum[n - 2];
    if (sum[n - 1] == 0) {
        return 0;
    }
    dist = std::max(dist, n - last);

    int j = 0;
    for (int i = (dist >> 1) + 1; i < dist; ++i) {
        if (n % i == 0) {
            last = 0;
            for (j = i; j <= n; j += i) {
                if (sum[j - 1] <= last) {
                    break;
                }
                last = sum[j - 1];
            }
            if (j > n) {
                return n / i;
            }
        }
    }

    for (last = dist; n % last != 0;) {
        ++last;
    }

    return n / last;
}

This finds the peak positions, then tests how many equal blocks can each contain at least one peak.

C# Peaks

static int Peaks(int[] a)
{
    var n = a.Length;
    if (n <= 2)
    {
        return 0;
    }

    var sum = new int[n];
    var last = -1;
    var dist = 0;

    for (int i = 1; i + 1 < n; i++)
    {
        sum[i] = sum[i - 1];
        if (a[i] > a[i - 1] && a[i] > a[i + 1])
        {
            dist = Math.Max(dist, i - last);
            last = i;
            sum[i]++;
        }
    }

    sum[n - 1] = sum[n - 2];
    if (sum[n - 1] == 0)
    {
        return 0;
    }

    dist = Math.Max(dist, n - last);

    for (int i = (dist >> 1) + 1; i < dist; i++)
    {
        if (n % i == 0)
        {
            last = 0;
            int j;
            for (j = i; j <= n; j += i)
            {
                if (sum[j - 1] <= last)
                {
                    break;
                }
                last = sum[j - 1];
            }
            if (j > n)
            {
                return n / i;
            }
        }
    }

    for (last = dist; n % last != 0;)
    {
        last++;
    }

    return n / last;
}

This finds the peak positions, then tests how many equal blocks can each contain at least one peak.

Elixir Peaks

defmodule Peaks do
  def peaks(a) when length(a) <= 2, do: 0

  def peaks(a) do
    n = length(a)
    a_map = a |> Enum.with_index() |> Map.new(fn {v, i} -> {i, v} end)

    {sum, dist, last_peak} = scan_peaks(a_map, n)
    total_peaks = Map.get(sum, n - 2, 0)
    sum = Map.put(sum, n - 1, total_peaks)

    if total_peaks == 0 do
      0
    else
      dist = max(dist, n - last_peak)

      case find_divisor(div(dist, 2) + 1, dist, n, sum) do
        {:ok, groups} -> groups
        :none -> div(n, find_valid_divisor(dist, n))
      end
    end
  end

  defp scan_peaks(a_map, n) do
    Enum.reduce(1..(n - 2), {%{0 => 0}, 0, -1}, fn i, {sum, dist, last} ->
      prev_sum = Map.get(sum, i - 1)

      is_peak =
        Map.get(a_map, i) > Map.get(a_map, i - 1) and
          Map.get(a_map, i) > Map.get(a_map, i + 1)

      if is_peak do
        {Map.put(sum, i, prev_sum + 1), max(dist, i - last), i}
      else
        {Map.put(sum, i, prev_sum), dist, last}
      end
    end)
  end

  defp find_divisor(i, dist, _n, _sum) when i >= dist, do: :none

  defp find_divisor(i, dist, n, sum) do
    if rem(n, i) == 0 do
      case walk_groups(i, i, n, sum, 0) do
        {:ok, last_j} when last_j > n -> {:ok, div(n, i)}
        _ -> find_divisor(i + 1, dist, n, sum)
      end
    else
      find_divisor(i + 1, dist, n, sum)
    end
  end

  defp walk_groups(j, _step, n, _sum, _last) when j > n, do: {:ok, j}

  defp walk_groups(j, step, n, sum, last) do
    current = Map.get(sum, j - 1)

    if current <= last do
      {:ok, j}
    else
      walk_groups(j + step, step, n, sum, current)
    end
  end

  defp find_valid_divisor(last, n) when rem(n, last) == 0, do: last
  defp find_valid_divisor(last, n), do: find_valid_divisor(last + 1, n)
end

This finds the peak positions, then tests how many equal blocks can each contain at least one peak.