A number of items are arranged on a long shelf (infinitely long, in fact) in a retail store. Each item's position can be described with an integral offset from some fixed point on the shelf.
There seems to be no order in how the items are currently arranged on the shelf. The store management, however, wants the shelf to be as aesthetically pleasing as possible in order to attract more customers. The management chooses to rearrange the items on the shelf so that they become equidistant, meaning that the distance between each pair of adjacent items is the same. The positions of all items must remain integers after rearranging, and no two items may occupy the same position.
Moving an item requires effort, which is measured as the absolute value of the distance that an item is moved. The management wants the items to be rearranged using the minimum possible amount of total effort, where total effort is the sum of efforts required to move each item.
Given a int[] initial, the current positions of the items on the shelf, return the minimum total effort required to make the items equidistant. |