Geek Answers Handbook

Optimize the solution for dividing the array into 3 parts by indices P, Q so that the cost is minimal

The problem is this:

  • The array contains N integers.
  • The index starts at 0.
  • We must split this array into 3 parts at breakpoints P and Q, where: 0 < P < Q < N-1 .
  • P and Q cannot be adjacent , that is: QP > 1 .
  • The cost of this violation is arr[P]+arr[Q] .

An array can be partitioned in many ways using various legal combinations of P and Q, each of which has its own costs. Find the minimum cost.

For example, an array

 arr = [5,2,4,6,3,7]

we can break the following:

 P, Q -----> Cost 1, 3 -----> 2 + 6 = 8 1, 4 -----> 2 + 3 = 5 2, 4 -----> 4 + 3 = 7

Therefore, the minimum cost = 5.

My current solution:

 public int solution(int[] A) { // code in Java SE 8 int len = A.length; int minCost = A[1]+A[3]; int cost; for(int p=1; p<len-3; p++){ for(int q = p+2; q<len-1; q++){ cost = A[p]+A[q]; if(cost < minCost){ minCost = cost; } } } return minCost; }

As you can see, the time complexity is O (N ^ 2), but for this requirement it is necessary that the solution be O (N). Can you suggest me how I can achieve this.

+5
source share
4 answers

This problem is needed only for the loop and one variable to maintain the last minimum element.

 int P = 1; int result = MAX_VALUE; for(int Q = 3; Q < n - 1; Q++){//Start the loop with Q = 3 result = min(result, data[Q] + data[P]); if(data[P] > data[Q - 1]){ //Update min only with the last element to maintain the constraint P - Q > 1 P = Q - 1; } } return result;

Time complexity: O (n), space complexity O (1)

+3
source

I would use recursion:

For each number N, recursively find the min numbers on the right, excluding the adjacent number and the lowest cost of the set of numbers on the right. N + min is the cost of setting your first break. You run away when you reach the last three numbers.

Hope this helps you, or at least you get started. From this, you can also create an iterative version with a bit more work.

 class Result { int minCost; int minNum; } Result findLowestCost (List<Integer> arr) { if (arr.size() == 4) { return (arr.get(0) + arr.get(2), min(arr.get(1), arr.get(2)); } int currNum = arr.get(0); // arr[P] Result result = findLowestCost(arr.subList(1)); int minCost = min(currNum + result.minNum, result.minCost); // arr[Q] int minNum = min(arr.get(1), result.minNum); return new Result(minCost, minNum; }
0
source

This is the problem of finding the three smallest numbers in an array:

 public int solution(int[] A) { // code in Java SE 8 int len = A.length; int min1 = A[0]; int min2 = A[1]; int min3 = A[2]; int pos1 = 0; int pos2 = 1; int pos3 = 2; if(min1>min2){ swap(min1,min2); swap(pos1,pos2); } if(min2>min3){ swap(min2,min3); swap(pos2,pos3); } if(min1>min2){ swap(min1,min2); swap(pos1,pos2); } //Now we have ordered mins: min1 <= mins <= min3 for(int p=3; p<len; p++){ if(min1 > A[p]){ min1 = A[p]; pos1 = p; } else if(min2 > A[p]){ min2 = A[p]; pos2 = p; } else if(min3 > A[p]){ min3 = A[p]; pos3 = p; } } //We kept ordered mins: min1 <= mins <= min3 if(abs(pos1-pos2) == 1){ return min1+min3; }else{ return min1+min2; } }

This is an algorithm. You need to add some statement regarding the length of the array.

0
source

Create two arrays,

  • For each index i calculate the minimum value up to (including) i . (Min_Upto [])
  • For each index i calculate the minimum value starting with (including) i . (Min_Starting_From [])

  • Then, in the third pass for each element, select index j , for which the following is minimal:

    Min_Upto [j-1] + Min_Starting_From [j + 1]

This will require 3 passes, and therefore the complexity of space and time should be O(N) .

0
source

More articles:


All Articles