Numbers

[typeof 42, typeof 4.2, typeof 42n];
// ["number", "number", "bigint"]
1e9 === 1_000_000_000; // true: 1e9 is an integer here
Number.isInteger(5.0); // true: 5.0 and 5 are one value
0.1 + 0.2; // 0.30000000000000004
2n ** 64n; // 18446744073709551616n
Number.MAX_SAFE_INTEGER; // 9007199254740991

const a = -7;
const b = 2;
[Math.trunc(a / b), Math.floor(a / b)]; // [-3, -4]
[a % b, ((a % b) + b) % b]; // [-1, 1]
 
// floored mod: the result takes the divisor's sign
const mod = (x: number, m: number): number =>
  ((x % m) + m) % m;
mod(-1, 5); // 4: index -1 wraps to the last slot
mod(12, 5); // 2
 
// ceiling division of non-negative integers
const ceilDiv = (x: number, y: number): number =>
  Math.floor((x + y - 1) / y);
ceilDiv(7, 2); // 4

const P = 2 ** 53;
P + 1 === P; // true
Number.isSafeInteger(P - 1); // true
Number.isSafeInteger(P); // false
 
const MOD = 1_000_000_007;
const x = 999_999_999;
(x * x) % MOD; // 63: x * x was rounded
Number((BigInt(x) * BigInt(x)) % BigInt(MOD)); // 64
 
BigInt.asIntN(32, 2n ** 31n); // -2147483648n
BigInt.asUintN(32, -1n); // 4294967295n
-7n / 2n; // -3n

const n = 10n;
try {
  // @ts-expect-error: TS2365, bigint + number
  n + 1;
} catch (e) {
  console.log((e as Error).name); // "TypeError"
}
n + 1n; // 11n
Number(n) + 1; // 11

const x = 12;
x & (x - 1); // 8: lowest set bit cleared
x & -x; // 4: lowest set bit alone
1 << 31; // -2147483648
1 << 32; // 1: the count is 32 % 32 = 0
-1 >>> 0; // 4294967295
(-5 >>> 0).toString(2).slice(-8); // "11111011"
31 - Math.clz32(40); // 5: floor(log2(40))
Math.imul(123456789, 987654321); // -67153019
(123456789 * 987654321) | 0; // -67153024: product rounded

function popcount(n: number): number {
  let count = 0;
  // >>> 0 so negative numbers count their 32 bits
  for (let v = n >>> 0; v !== 0; v &= v - 1) count++;
  return count;
}
 
// the same with no loop: add bits in pairs, nibbles, bytes
function popcount32(x: number): number {
  x -= (x >>> 1) & 0x55555555;
  x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
  x = (x + (x >>> 4)) & 0x0f0f0f0f;
  return Math.imul(x, 0x01010101) >>> 24;
}
 
[popcount(13), popcount(-1), popcount32(255)]; // [3, 32, 8]

const items = ["a", "b", "c"];
const subsets: string[][] = [];
for (let mask = 0; mask < 1 << items.length; mask++) {
  subsets.push(items.filter((_, i) => (mask >> i) & 1));
}
subsets.length; // 8
subsets[5]; // ["a", "c"]: mask 0b101

(0.1).toString(2).slice(0, 22);
// "0.00011001100110011001"
0.1 + 0.2 === 0.3; // false
Math.abs(0.1 + 0.2 - 0.3) < 1e-9; // true
(1.005).toPrecision(20); // "1.0049999999999998934"

function sqrtBisect(v: number): number {
  let lo = 0;
  let hi = Math.max(1, v);
  for (let i = 0; i < 100; i++) {
    const mid = (lo + hi) / 2;
    if (mid * mid < v) lo = mid;
    else hi = mid;
  }
  return hi;
}
sqrtBisect(2) === Math.SQRT2; // true

function gcd(a: number, b: number): number {
  while (b !== 0) [a, b] = [b, a % b];
  return Math.abs(a);
}
 
const lcm = (a: number, b: number): number =>
  (a / gcd(a, b)) * b; // divide first: smaller product
 
// exact floor(sqrt(n)) for any safe integer n
function isqrt(n: number): number {
  let r = Math.floor(Math.sqrt(n));
  while (r * r > n) r--;
  while ((r + 1) * (r + 1) <= n) r++;
  return r;
}
 
[gcd(12, 18), gcd(0, 5), gcd(-4, 6)]; // [6, 5, 2]
lcm(4, 6); // 12
Math.floor(Math.sqrt(4503599761588224)); // 67108865
isqrt(4503599761588224); // 67108864

const MOD = 1_000_000_007;
 
// exact a * b % m for 0 <= a, b < m < 2 ** 30
function mulmod(a: number, b: number, m: number): number {
  const hi = (a * (b >>> 16)) % m; // high part of b
  return (hi * 65536 + a * (b & 65535)) % m;
}
 
function modPow(b: number, e: number, m: number): number {
  let result = 1;
  b %= m;
  // Math.floor(e / 2), not e >> 1: e can pass 2 ** 31
  for (; e > 0; e = Math.floor(e / 2)) {
    if (e % 2 === 1) result = mulmod(result, b, m);
    b = mulmod(b, b, m);
  }
  return result;
}
 
mulmod(999_999_999, 999_999_999, MOD); // 64
modPow(2, 1e18, MOD); // 719476260
const inv3 = modPow(3, MOD - 2, MOD);
mulmod(6, inv3, MOD); // 2: "6 / 3" mod p
((3 - 5) % MOD + MOD) % MOD; // 1000000005

function modPowBig(b: bigint, e: bigint, m: bigint): bigint {
  let result = 1n;
  b %= m;
  for (; e > 0n; e >>= 1n) {
    if (e & 1n) result = (result * b) % m;
    b = (b * b) % m;
  }
  return result;
}
modPowBig(2n, 10n ** 18n, 1_000_000_007n); // 719476260n

const n = 9045;
[...String(n)].map(Number); // [9, 0, 4, 5]
 
const digits: number[] = [];
for (let m = n; m > 0; m = Math.floor(m / 10)) {
  digits.push(m % 10); // least significant first
}
digits; // [5, 4, 0, 9]
digits.reduce((s, d) => s + d, 0); // 18
Number([9, 0, 4, 5].join("")); // 9045
["1", "2", "3"].map(Number); // [1, 2, 3]

const counts = new Int32Array(26); // zero-filled
for (const ch of "banana") counts[ch.charCodeAt(0) - 97]++;
[counts[0], counts[1], counts[13]]; // [3, 1, 2]
 
new Int32Array([10, 9, 1, 2]).sort(); // [1, 2, 9, 10]
[10, 9, 1, 2].sort(); // [1, 10, 2, 9]: string order
 
const cell = new Int32Array(1);
cell[0] = 2 ** 31; // stored through ToInt32
cell[0]; // -2147483648
 
const buf = new Uint8Array([1, 2, 3, 4]);
const view = buf.subarray(1, 3); // shares memory
view[0] = 9;
buf; // [1, 9, 3, 4]

const cols = 4;
const i = 7;
[Math.floor(i / cols), i % cols]; // [1, 3]
 
const lo = 2 ** 30;
const hi = 2 ** 30 + 10;
(lo + hi) >> 1; // -1073741819: lo + hi passed 2 ** 31
(lo + hi) >>> 1; // 1073741829
lo + Math.floor((hi - lo) / 2); // 1073741829
 
const isPow2 = (n: number): boolean =>
  n > 0 && (n & (n - 1)) === 0;
[isPow2(64), isPow2(96), isPow2(0)]; // [true, false, false]
-7 % 2 === 1; // false: -7 is odd, but % gives -1
(-7 & 1) === 1; // true

type NodeId = number & { readonly __brand: "NodeId" };
const nodeId = (n: number): NodeId => n as NodeId;
 
function dist(from: NodeId, to: NodeId): number {
  return Math.abs(from - to);
}
const a = nodeId(3);
dist(a, nodeId(7)); // 4
// @ts-expect-error: a plain number is not a NodeId
dist(a, 7);
 
const DIRS = [[0, 1], [1, 0], [0, -1], [-1, 0]] as const;
type Step = (typeof DIRS)[number]; // readonly [0, 1] | ...
const sign = (x: number): -1 | 0 | 1 =>
  x < 0 ? -1 : x > 0 ? 1 : 0;
[sign(-4), sign(0), sign(9)]; // [-1, 0, 1]
 
const Color = { Red: 0, Green: 1 } as const;
type Color = (typeof Color)[keyof typeof Color]; // 0 | 1
const c: Color = Color.Green; // 1

function primesUpTo(n: number): number[] {
  if (n < 2) return [];
  const composite = new Uint8Array(n + 1); // all 0
  const primes: number[] = [];
  for (let p = 2; p <= n; p++) {
    if (composite[p]) continue;
    primes.push(p);
    for (let m = p * p; m <= n; m += p) composite[m] = 1;
  }
  return primes;
}
 
primesUpTo(30);
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
primesUpTo(1e6).length; // 78498

function factorize(n: number): Map<number, number> {
  const f = new Map<number, number>();
  for (let d = 2; d * d <= n; d += d === 2 ? 1 : 2) {
    while (n % d === 0) {
      f.set(d, (f.get(d) ?? 0) + 1);
      n /= d;
    }
  }
  if (n > 1) f.set(n, (f.get(n) ?? 0) + 1); // a prime
  return f;
}
 
const f = factorize(360); // Map(3) {2 => 3, 3 => 2, 5 => 1}
let divisors = 1;
for (const e of f.values()) divisors *= e + 1;
divisors; // 24

const MOD = 1_000_000_007;
const N = 100_000;
 
function mulmod(a: number, b: number, m: number): number {
  const hi = (a * (b >>> 16)) % m;
  return (hi * 65536 + a * (b & 65535)) % m;
}
 
function modPow(b: number, e: number, m: number): number {
  let r = 1;
  for (; e > 0; e = Math.floor(e / 2)) {
    if (e % 2 === 1) r = mulmod(r, b, m);
    b = mulmod(b, b, m);
  }
  return r;
}
 
const fact = new Array<number>(N + 1).fill(1);
for (let i = 1; i <= N; i++) {
  fact[i] = mulmod(fact[i - 1], i, MOD);
}
const invFact = new Array<number>(N + 1).fill(1);
invFact[N] = modPow(fact[N], MOD - 2, MOD); // Fermat
for (let i = N; i > 0; i--) {
  invFact[i - 1] = mulmod(invFact[i], i, MOD);
}
 
function nCr(n: number, r: number): number {
  if (r < 0 || r > n) return 0;
  const top = mulmod(fact[n], invFact[r], MOD);
  return mulmod(top, invFact[n - r], MOD);
}
 
[nCr(5, 2), nCr(100_000, 50_000)]; // [10, 149033233]

const INT_MAX = 2 ** 31 - 1;
const INT_MIN = -(2 ** 31);
 
function reverseInt(x: number): number {
  let n = Math.abs(x); // -123 % 10 would be -3
  let r = 0;
  while (n > 0) {
    r = r * 10 + (n % 10);
    n = Math.floor(n / 10);
  }
  if (x < 0) r = -r;
  return r < INT_MIN || r > INT_MAX ? 0 : r;
}
 
[reverseInt(-123), reverseInt(120)]; // [-321, 21]
reverseInt(1534236469); // 0: 9646324351 overflows

const addBinary = (a: string, b: string): string =>
  (BigInt(`0b${a}`) + BigInt(`0b${b}`)).toString(2);
 
addBinary("1011", "11"); // "1110"
addBinary("1".repeat(100), "1").length; // 101
(255n).toString(16); // "ff"
BigInt("0xff"); // 255n

function countBits(n: number): number[] {
  const bits = new Array<number>(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    bits[i] = bits[i >> 1] + (i & 1); // drop the last bit
  }
  return bits;
}
 
countBits(5); // [0, 1, 1, 2, 1, 2]

type Mat = readonly [number, number, number, number];
 
function mulmod(a: number, b: number, m: number): number {
  const hi = (a * (b >>> 16)) % m;
  return (hi * 65536 + a * (b & 65535)) % m;
}
 
function matMul(x: Mat, y: Mat, m: number): Mat {
  const [a, b, c, d] = x; // [[a, b], [c, d]]
  const [e, f, g, h] = y;
  const mm = (p: number, q: number, r: number, s: number) =>
    (mulmod(p, q, m) + mulmod(r, s, m)) % m;
  return [
    mm(a, e, b, g),
    mm(a, f, b, h),
    mm(c, e, d, g),
    mm(c, f, d, h),
  ];
}
 
function fib(n: number, m = 1_000_000_007): number {
  let result: Mat = [1, 0, 0, 1]; // identity
  let base: Mat = [1, 1, 1, 0];
  for (; n > 0; n = Math.floor(n / 2)) {
    if (n % 2 === 1) result = matMul(result, base, m);
    base = matMul(base, base, m);
  }
  return result[1]; // base ** n = [[F(n+1), F(n)], ...]
}
 
Array.from({ length: 10 }, (_, i) => fib(i));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fib(1e18); // 209783453

type Pt = readonly [number, number];
 
function gcd(a: number, b: number): number {
  while (b !== 0) [a, b] = [b, a % b];
  return Math.abs(a);
}
 
function direction(dx: number, dy: number): string {
  const g = gcd(dx, dy); // > 0 unless both are 0
  dx /= g;
  dy /= g;
  if (dx < 0 || (dx === 0 && dy < 0)) {
    dx = -dx; // one sign per direction
    dy = -dy;
  }
  return `${dx},${dy}`; // `${-0}` is "0"
}
 
function maxPoints(pts: readonly Pt[]): number {
  let best = Math.min(pts.length, 1);
  pts.forEach(([x1, y1], i) => {
    const dirs = new Map<string, number>();
    for (const [x2, y2] of pts.slice(i + 1)) {
      const key = direction(x2 - x1, y2 - y1);
      const c = (dirs.get(key) ?? 0) + 1;
      dirs.set(key, c);
      best = Math.max(best, c + 1);
    }
  });
  return best;
}
 
const pts: Pt[] = [
  [1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4],
];
maxPoints(pts); // 4