Cody

Problem 42834. Integer complexity (Large numbers)

Created by Peng Liu in Community

Inspired by Problem 42831, this problem aims to calculate the integer complexity for large numbers. The integer complexity of a natural number n is defined as the least number of 1’s required to express n using only the two operations + and × and parentheses.

Example: the number 11 may be represented using 8 ones:

    11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

However, it has no representation using 7 or fewer ones. Therefore, its complexity is 8.

Your solution will be scored based on its running time. No cheating please.

Solution Stats

50.0% Correct | 50.0% Incorrect
Last solution submitted on Dec 14, 2018