SDE - Intern

You are given a positive integer 'N’. Your task is to find and return the minimum number of steps that 'N' has to take to get reduced to 1.

You can perform any one of the following 3 steps:

1) Subtract 1 from it. (n = n - ­1) ,
2) If n is divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2 ) ,
3) If n is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3 ).

For example:

Given:
‘N’ = 4, it will take 2 steps to reduce it to 1, i.e., first divide it by 2 giving 2 and then subtract 1, giving 1.

Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ‘K’ numbers in a particular window at a time. For each of the 'N'-'K'+1 different windows thus formed, you are supposed to return the maximum element in each of them, from the given array/list.

Given an array ‘arr’ consisting of ‘N’ integer elements. You have to remove ‘K’ elements from the beginning or end of the array. Return the maximum possible sum of the remaining array elements.

Note: you can remove elements from both beginning and end, but a total of ‘K’ elements must be removed.

Example :

If N = 7 and K = 3, and the input array is:
{1, 2, 3, 4, 5, 6, 7}

After removing the first three elements, the resulting array now becomes {4, 5, 6, 7} and the sum of the remaining array is equal to 22.

Removing any other combination of three elements will always result in the remaining array sum less than 22.