Calculator Keystrokes

Computer Science Level 4

Tyler has two calculators, both of which initially display zero. The first calculator has only two buttons, $[+1]$ and $[\times 2]$ . The second has only the buttons $[+1]$ and $[\times 4]$ . Both calculators update their displays immediately after each keystroke.

A positive integer $n$ is called ambivalent if the minimum number of keystrokes needed to display $n$ on the first calculator equals the minimum number of keystrokes needed to display $n$ on the second calculator. Find the last three digits of the $2014^\text{th}$ smallest ambivalent number.

The answer is 946.

1 solution

Piotr Idzik
May 19, 2020

My python code using dynamic programming.

"""
solution of:
    https://brilliant.org/problems/calculator-keystrokes/
"""

class Calc:
    """
    represents a "calculator" from the puzzle:
        https://brilliant.org/problems/calculator-keystrokes/
    which has two buttons: +1 and *self.multip
    """
    def __init__(self, multip):
        self.multip = multip
        self.res_data = {0:0, 1:1}
    def get_number_of_steps(self, in_val):
        """
        returns the minimum number of steps keystrokes needed to display in_val
        """
        if in_val in self.res_data:
            res = self.res_data[in_val]
        else:
            res_a = self.get_number_of_steps(in_val-1)
            res_b = res_a
            if in_val%self.multip == 0:
                res_b = self.get_number_of_steps(in_val//self.multip)
            res = 1+min([res_a, res_b])
            self.res_data[in_val] = res
        return res

CALC_A = Calc(2)
CALC_B = Calc(4)

FOUND_NUM = 0
CUR_N = 0
LIMIT_N = 2014
while FOUND_NUM < LIMIT_N:
    CUR_N += 1
    if CALC_A.get_number_of_steps(CUR_N) == CALC_B.get_number_of_steps(CUR_N):
        FOUND_NUM += 1
print(f"The {LIMIT_N}th ambivalent number is: {CUR_N} -> solution: {CUR_N%1000}")

Calculator Keystrokes

The answer is 946.

1 solution

0 pending reports