Notes

Rust Count Factors

fn count_factors(n: i64) -> i64 {
    let mut count = 0;
    let mut i = 1i64;
    while i * i < n {
        if n % i == 0 {
            count += 2;
        }
        i += 1;
    }
    if i * i == n {
        count += 1;
    }

    count
}

This checks divisors in pairs up to the square root, which keeps the work much smaller than testing every number.

TypeScript Count Factors

function countFactors(n: number): number {
  let count = 0;
  let i = 1;
  while (i * i < n) {
    if (n % i === 0) {
      count += 2;
    }
    i++;
  }
  if (i * i === n) {
    ++count;
  }

  return count;
}

This checks divisors in pairs up to the square root, which keeps the work much smaller than testing every number.

Bash Count Non Divisible

count_non_divisible() {
    local -n _a="$1"
    local -n _out="$2"
    local _size=${#_a[@]}
    local _maxv=${_a[0]} _v
    for _v in "${_a[@]}"; do (( _v > _maxv )) && _maxv=$_v; done
    local -a _occ
    for ((_v = 0; _v <= _maxv; _v++)); do _occ[_v]=0; done
    for _v in "${_a[@]}"; do _occ[_v]=$(( _occ[_v] + 1 )); done
    _out=()
    local _k
    for _k in "${!_a[@]}"; do
        _v=${_a[$_k]}
        local _count=0 _i=1
        while (( _i * _i <= _v )); do
            if (( _v % _i == 0 )); then
                _count=$(( _count + _occ[_i] ))
                if (( _v / _i != _i )); then
                    _count=$(( _count + _occ[_v/_i] ))
                fi
            fi
            ((_i++))
        done
        _out[_k]=$(( _size - _count ))
    done
}

This counts how often each value appears, then subtracts the divisor matches so you get the non-divisible count for each item.

C++ Count Non Divisible

#include <algorithm>
#include <vector>

std::vector<int> countNonDivisible(const std::vector<int>& a)
{
    int size = static_cast<int>(a.size());
    std::vector<int> nondivisor(size, 0);

    int maxVal = *std::max_element(a.begin(), a.end());
    std::vector<int> occurrences(maxVal + 1, 0);

    for (int v : a) {
        ++occurrences[v];
    }

    for (int k = 0; k < size; ++k) {
        int v = a[k];
        int count = 0;
        long long i = 1;
        while (i * i <= v) {
            if (v % i == 0) {
                count += occurrences[i];
                if (v / i != i) {
                    count += occurrences[v / i];
                }
            }
            ++i;
        }
        nondivisor[k] = size - count;
    }

    return nondivisor;
}

This counts how often each value appears, then subtracts the divisor matches so you get the non-divisible count for each item.

C# Count Non Divisible

static int[] CountNonDivisible(int[] a)
{
    var size = a.Length;
    var nondivisor = new int[size];
    var occurrences = new int[a.Max() + 1];

    foreach (var v in a)
    {
        occurrences[v]++;
    }

    for (int k = 0; k < size; k++)
    {
        var v = a[k];
        var count = 0;
        var i = 1;
        while (i * i <= v)
        {
            if (v % i == 0)
            {
                count += occurrences[i];
                if (v / i != i)
                {
                    count += occurrences[v / i];
                }
            }
            i++;
        }
        nondivisor[k] = size - count;
    }

    return nondivisor;
}

This counts how often each value appears, then subtracts the divisor matches so you get the non-divisible count for each item.

Elixir Count Non Divisible

defmodule CountNonDivisible do
  def count_non_divisible(a) do
    size = length(a)
    occurrences = Enum.frequencies(a)

    Enum.map(a, fn v -> size - divisor_occurrences(1, v, occurrences, 0) end)
  end

  defp divisor_occurrences(i, v, _occurrences, count) when i * i > v, do: count

  defp divisor_occurrences(i, v, occurrences, count) do
    count =
      if rem(v, i) == 0 do
        count = count + Map.get(occurrences, i, 0)

        if div(v, i) != i do
          count + Map.get(occurrences, div(v, i), 0)
        else
          count
        end
      else
        count
      end

    divisor_occurrences(i + 1, v, occurrences, count)
  end
end

This counts how often each value appears, then subtracts the divisor matches so you get the non-divisible count for each item.

Erlang Count Non Divisible

-module(count_non_divisible).
-export([count_non_divisible/1]).

count_non_divisible(A) ->
    Size = length(A),
    Occ = lists:foldl(fun(V, Map) ->
        maps:update_with(V, fun(C) -> C + 1 end, 1, Map)
    end, #{}, A),
    [Size - count_divisors(V, Occ) || V <- A].

count_divisors(V, Occ) ->
    count_divisors(V, Occ, 1, 0).

count_divisors(V, _Occ, I, Count) when I * I > V ->
    Count;
count_divisors(V, Occ, I, Count) ->
    case V rem I of
        0 ->
            Base = Count + maps:get(I, Occ, 0),
            Total = case V div I =:= I of
                true -> Base;
                false -> Base + maps:get(V div I, Occ, 0)
            end,
            count_divisors(V, Occ, I + 1, Total);
        _ ->
            count_divisors(V, Occ, I + 1, Count)
    end.

This counts how often each value appears, then subtracts the divisor matches so you get the non-divisible count for each item.

Go Count Non Divisible

func countNonDivisible(a []int) []int {
	size := len(a)
	nonDivisors := make([]int, size)

	maxVal := a[0]
	for _, v := range a {
		if v > maxVal {
			maxVal = v
		}
	}

	occurrences := make([]int, maxVal+1)
	for _, v := range a {
		occurrences[v]++
	}

	for k, v := range a {
		count := 0
		for i := 1; i*i <= v; i++ {
			if v%i == 0 {
				count += occurrences[i]
				if v/i != i {
					count += occurrences[v/i]
				}
			}
		}
		nonDivisors[k] = size - count
	}

	return nonDivisors
}

This counts how often each value appears, then subtracts the divisor matches so you get the non-divisible count for each item.

Haskell Count Non Divisible

import qualified Data.Map.Strict as Map

countNonDivisible :: [Int] -> [Int]
countNonDivisible a = map (\v -> size - divisorCount v) a
  where
    size = length a
    occ  = Map.fromListWith (+) [(v, 1 :: Int) | v <- a]
    occCount v = Map.findWithDefault 0 v occ

    divisorCount v =
      sum
        [ occCount i + (if v `div` i /= i then occCount (v `div` i) else 0)
        | i <- takeWhile (\i -> i * i <= v) [1 ..]
        , v `mod` i == 0
        ]

This counts how often each value appears, then subtracts the divisor matches so you get the non-divisible count for each item.

Java Count Non Divisible

import java.util.Arrays;

public class Solution {
    public static int[] countNonDivisible(int[] a) {
        int size = a.length;
        int[] nondivisor = new int[size];
        int maxValue = Arrays.stream(a).max().orElse(0);
        int[] occurrences = new int[maxValue + 1];

        for (int v : a) {
            occurrences[v]++;
        }

        for (int k = 0; k < size; k++) {
            int v = a[k];
            int count = 0;
            long i = 1;
            while (i * i <= v) {
                if (v % i == 0) {
                    count += occurrences[(int) i];
                    if (v / i != i) {
                        count += occurrences[(int) (v / i)];
                    }
                }
                i++;
            }
            nondivisor[k] = size - count;
        }

        return nondivisor;
    }
}

This counts how often each value appears, then subtracts the divisor matches so you get the non-divisible count for each item.

20
21
22
23
24