Company: DeShaw_28thjune
Difficulty: medium
An accounting firm records all the transactions in a linear sequence. Each transaction can have an integer value, and the goal for a clean audit is to adjust all transactions so that every value becomes zero. The firm has a tool that can perform a switch operation and adjust the value of a sequence of transactions. In one switch, it can select a contiguous group of transactions from the start and either add or subtract one unit of value from each transaction in the group. Find the minimum number of switch required to convert every transaction to 0. Note: It is guaranteed that it is always possible to convert every element of the array to 0. Example transactions = [3, 2, 1] The most efficient approach is: Operation 1: Select the prefix of length 2, and decrement by 1. transactions after this switch is [2, 1, 1]. Operation 2: Select the prefix of length 1, and decrement by 1. transactions after this switch is [1, 1, 1]. Operation 3: Select the prefix of length 3, and decrement by 1. tran