This page is still under construction.

Parts of this page are still being built. What you see may change.

Double and Add

Interview

Time limit2sMemory limit512 MB

Summary
Starting from an all-zero array, find the minimum number of single-element increments and whole-array doublings that produce the target array B.
Level

Medium5 of 10

Topics
Greedy, Bit manipulation, Math, Implementation
Solved
No attempts yet

Problem

You have an array AA of length NN whose every element is 0. You can perform these two operations.

  • Increase one element of the array by 1.
  • Double every element of the array.

Given an array BB, write a program that finds the minimum number of operations needed to make AA equal to BB.

Input

The first line contains the size of the array, NN. (1≤N≤501 \le N \le 50)

The second line contains the NN elements of BB, separated by spaces. Each element is an integer between 0 and 1,000, inclusive.

Output

Print the minimum number of operations that turns AA into BB on the first line.

Examples4

  1. Example 1

    Input
    2
2 1
    Expected output
    3

  2. Example 2

    Input
    3
16 16 16
    Expected output
    7

  3. Example 3

    Input
    1
100
    Expected output
    9

  4. Example 4

    Input
    5
0 0 1 0 1
    Expected output
    2