This was an online coding task which I attempted some days back. I have an Array of size N. Items in the array together indicate a chain, now each item indicates the power of each connection in the chain. The task is to divide the chain into 3 smaller chains.

Task is to break the chain in exactly two non-adjacent positions. It means we have to break connections A,B (0<A<B<N-1,B-A>1), resulting in three chains [0,A-1],[A 1,B-1],[B 1,N-1]. So the total cost of this operation is equal to array[A] array[B].

For example:

Array = {5, 2, 4, 6, 3, 7}

Array[0]=5
Array[1]=2
Array[2]=4
Array[3]=6
Array[4]=3
Array[5]=7

Output:

5

Explanation:

We can choose to break the following connections:

(1, 3): total cost is 2   6 = 8
(1, 4): total cost is 2   3 = 5
(2, 4): total cost is 4   3 = 7

Hence a minimum of (8, 5, 7) is 5.

Constraints: N is Array size in range [5..100,000]; Each Array item range is [1..1,000,000,000].

I am not sure if my understanding is correct or not. This is my idea. Basically, find positions A and B in the Array such that both are non-adjacent and get the sum of items Array[A] Array[B] and check for the minimum sum.

This is my code.

public int solution(int[] Array ) { 
    long output = 0;
    int N = Array.length;
    for(int i=0; i<N-1; i  ) {
        for(int j=i 2; j<N; j  ) {
            long sum = Array[i]   Array[j];
            if(output > sum) {
                output = sum;
            }
        }
    }
    return (int) output;
}

This code gave the correct output for the example I mentioned. But the online coding task had several hidden inputs for which the code failed completely.

CodePudding user response：

Your code is wrong:

• Instead of i=0 you should start with i=1.
• Instead of j<N you should limit with j<N-1.

It's also very slow, takes quadratic time. Should be solved in linear time. Just go over all possible B-values and combine each with the smallest A-value allowed thus far (Try it online!):

public int solution(int[] Array ) {
    int a = Array[1], output = a   Array[3], N = Array.length;
    for (int B=4; B<N-1; B  ) {
        a = Math.min(a, Array[B-2]);
        output = Math.min(output, a   Array[B]);
    }
    return output;
}

Note that while I do usually prefer index variables i and j, that gets trumped by the problem description calling them A and B. So I use B here (and I don't need A).

Or in Python (Try it online!):

def solution(array):
    return min(map(add, accumulate(array[1:], min), array[3:-1]))

CodePudding user response：

You have the input data which the code failed? If your code work maybe try:

for(int i=0; i<N; i  ) {
        for(int j=2; j<N; j  ) {
            if(j - i !=  -1 || j - i != 1) {
            long sum = Array[i]   Array[j];
              if(output > sum) {
                  output = sum;
              }
           }
        }
    }

But with out data which is not work i guess.