0
\$\begingroup\$

Given a binary string equivalent to \$n\$, write out the least possible number of terms needed to express \$n\$.

A term is defined as an addition of either \$2^k\$ or \$(-2^k)\$, where \$k\$ is a non-negative integer.

Sample I/O

# BinaryString -> Output

1101101 -> 4

110101101 -> 5

1010110110 -> 5

110000101101 -> 6

101010101101101101011011101011010101101 -> 17

101010101101101010101010101101101101011011101011010101101101101101101011011101011010101101101010101101101101011011101011010101101101101010101110101010110110110101101110101101010110101010101011011011010110111010110101011011101101011011101011010101101101011011101011010101101 -> 107

Explanation

For the first sample: consider the string \$1101101\$, its decimal equivalent number \$n\$ is \$109\$,
which is most optimally expressed as \$2^7 + (-2^4)+(-2^2)+2^0\$ (4 terms).

Constraint

\$n ≤ 2^{1000000}\$

Winning Criterion

The binary string for runtime comparison will be, in Python3:
"{0:b}".format(9515985770616618967204423793474873711653 * 10 ** 300990)
Output: 233542

This is a fastest-code challenge, lowest runtime performance for the given binary string wins!
The timing will be done on my machine and this is a competition per language.

STANDINGS

Fastest Code Language Runtime Performance
Arnauld node.js 475 ± 42 ms
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Welcome to Code Golf and nice first question! For future reference, we recommend using the Sandbox to get feedback on challenge ideas before posting them to main. As this site supports MathJax I've replaced the images with that for better accessibility. Also, since this is a [fastest-code] challenge, you'll need to specify some sort of benchmark, which usually is timing the solutions on your own computer. \$\endgroup\$
    – emanresu A
    Commented Jun 10 at 0:09
  • 14
    \$\begingroup\$ Please do not vandalize your posts. By posting on the Stack Exchange network, you've granted a non-revocable right for SE to distribute that content (under the CC BY-SA 4.0 license). By SE policy, any vandalism will be reverted. \$\endgroup\$
    – tripleee
    Commented Jun 10 at 6:20
  • 2
    \$\begingroup\$ Negative powers in the title is confusing. It may sound like 2^(-4)' rather than the intended -(2^4). I suggest Addition or subtraction of powers of 2 \$\endgroup\$
    – Luis Mendo
    Commented Jun 10 at 8:35

3 Answers 3

3
\$\begingroup\$

JavaScript (Node.js), ≈3.3ms (1)

This hexadecimal version was suggested by tsh

Expects a BigInt.

This computes hammingweight(XOR(n, 3*n)), as suggested on A007302.

function f(binStr) {
  const tableHex = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 2, 3, 2, 3, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  ];

  const n = BigInt("0b" + binStr);
  const hex = (n ^ 3n * n).toString(16);
  let count = 0;
  for (let i = 0, l = hex.length; i < l; ++i) {
    count += tableHex[hex.charCodeAt(i)];
  }
  return count;
}

Try it online!


Using binary, ≈16ms (1)

function f(binStr) {
  const n = BigInt("0b" + binStr);
  let bin = (n ^ 3n * n).toString(2);

  return bin.split("1").length - 1;
}

Try it online!

Bitwise approach, ≈12 seconds (1)

Converting to a binary or hexadecimal string and iterating over its characters may not be the most elegant method (conceptually speaking), but it's much, much faster than going bitwise.

I assume this one causes several new BigInts to be allocated, inducing a massive overhead in the pipeline when n is large.

function f(binStr) {
  const n = BigInt("0b" + binStr);
  let N = n ^ 3n * n,
      count = 0;

  while(N) {
    N &= N - 1n;
    count++;
  }
  return count;
}

Try it online!


(1) All benchmarks were done on my laptop with Node 20.10.0, using several calls to the function in a loop.

\$\endgroup\$
16
  • \$\begingroup\$ (n + n + n) should save some over 3n * n (seems to be unnoticeable for even the large test case on TIO though! Is it optimised by compilation maybe?) \$\endgroup\$ Commented Jun 10 at 12:48
  • 1
    \$\begingroup\$ @JonathanAllan The V8 engine has 4 dedicated modules for BigInt multiplications (mul-fft.cc, mul-karatsuba.cc, mul-schoolbook.cc, mul-toom.cc) which are chosen according to the operands. So I'm sure it's already pretty well optimized. \$\endgroup\$
    – Arnauld
    Commented Jun 10 at 13:09
  • 1
    \$\begingroup\$ (Also, even if an operation on a BigInt does not map directly to a single CPU instruction, the cost of an addition is still likely to be significantly more than that of a shift. So I think the best strategy is (n << 1) + n.) \$\endgroup\$
    – Arnauld
    Commented Jun 10 at 13:16
  • \$\begingroup\$ Convert to hex seems to be faster on TIO, could you have another test on your machine? hex approach \$\endgroup\$
    – tsh
    Commented Jun 11 at 3:07
  • 1
    \$\begingroup\$ and another one \$\endgroup\$
    – tsh
    Commented Jun 11 at 3:18
2
\$\begingroup\$

Rust + num_bigint 0.4.5

use num_bigint::BigUint;
use std::str::FromStr;

fn main() {
    let input = BigUint::from_str("9515985770616618967204423793474873711653").unwrap()
        * (BigUint::from(10u64).pow(300990));
    print!("{}", f(input))
}

fn f(n: BigUint) -> u64 {
    let bin: BigUint = &n ^ (&n + (&n << 1));
    bin.count_ones()
}

For the best performance, make sure to compile with
RUSTFLAGS='-C target-cpu=native' cargo build --release. It is around 20ms on my machine.

\$\endgroup\$
0
\$\begingroup\$

Python + gmpy2   2.1.5

import gmpy2
from gmpy2 import mpz
import time

def main():
    input_value = mpz('9515985770616618967204423793474873711653') * (mpz(10) ** 300990)
    print(f(input_value))

def f(n):
    bin_value = n ^ (n + (n << 1))
    return gmpy2.popcount(bin_value)

if __name__ == "__main__":
    start_time=time.time()
    main()
    print(f"{(time.time()-start_time)*1000} ms")

It is around 16ms on my machine.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.