Find absolute sum of minimum slice - codility [duplicate]

Question

Hi I've taken Codility test twice and scored 0. Please help me in solving the issue using JavaScript.

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

A min abs slice is whose absolute sum is minimal.

For example, array A such that:

A[0] = 2
A[1] = -4
A[2] = 6
A[3] = -3
A[4] = 9

contains the following slice among others:

(0,1), whose absolute sum is = |2 + (-4)| = 2
(0,2), whose absolute sum is = |2 + (-4) + 6| = 4
(0,3), whose absolute sum is = |2 + (-4) + 6 + (-3)| = 1
(1,3), whose absolute sum is = |(-4) + 6 + (-3)| = 1
(1,4), whose absolute sum is = |(-4) + 6 + (-3) + 9| = 8
(4,4), whose absolute sum is = |9| = 9

Both slices (0,3) and (1,3) are min abs slice and their absolute sum equals 1.

Write a function:

function solution(A);

that, given a non-empty array A consisting of N integers, return the absolute sum of min abs slice.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..1,000,000];
each element of array A is an integer within the range [−10,000..10,000];

Here is my solution:

function solution(A, i = 0, sum = 0) {
  const N = A.length;
  if (N === 0) {
    return 0;
  }
  if (N == 1) {
    return Math.abs(A[0]);
  }
  A.sort();

  // All positives 
  if (A[0] >= 0 && A[N - 1] >= 0) {
    return Math.abs(A[0]);
  }
  // All Negatives
  if (A[0] <= 0 && A[N - 1] <= 0) {
    return Math.abs(A[N - 1]);
  }
  let currAbsSum = 0;
  let minAbsSum = Number.MAX_SAFE_INTEGER;
  for (var i = 0; i < N; i++) {
    let j = N - 1;
    while (j >= i) {
      currAbsSum = Math.abs(A[i] + A[j]);
      if (currAbsSum === 0) {
        return 0;
      }
      minAbsSum = Math.min(currAbsSum, minAbsSum);
      if (Math.abs(A[i]) > Math.abs(A[j])) {
        i++;
      } else {
        j--;
      }
    }
    if (A[i] > 0) break;
  }
  return minAbsSum;
}

Firstly, JavaScript and java are entirely different. Choose one. Second, you’ve provided no effort, just a problem, so therefore this will likely get downvoted and closed. — achAmháin
– achAmháin, Commented Aug 28, 2018 at 18:47
Jeesh, the wording of that question is all over the place. Share a link to the original question. — Geuis
– Geuis, Commented Aug 28, 2018 at 18:49
@achAmháin Thanks for you swift response. I know the difference between Java & JavaScript and also I've already tried alot but unable solve it that why I've posted here. Here is my score. — Anand Dev Singh
– Anand Dev Singh, Commented Aug 28, 2018 at 18:53
@Geuis, It is a paid test and I can't open the link again as I've taken the test. Though If you want the code I wrote then I can add that in the post. — Anand Dev Singh
– Anand Dev Singh, Commented Aug 28, 2018 at 18:56
First thing you do is sort the array, that already makes all the following logic invalid, changing the order of the input changes the slices you can make — juvian
– juvian, Commented Aug 28, 2018 at 19:31

HCSF · Accepted Answer · 2019-11-13 04:31:16Z

2

Here is a javascript version of O(n log n) answer taken from here:

function solution(A) {
	if (1 == A.length) return Math.abs(A[0]);

	let sums = new Array(A.length + 1);
	let minAbsSum = Number.MAX_SAFE_INTEGER;

	sums[0] = 0;
	
	for (var i = 0; i < A.length; i++) {
		sums[i + 1] = A[i] + sums[i];
	}

	sums.sort();

	for (var i = 1; i < sums.length; i++) {
		minAbsSum = Math.min(minAbsSum, Math.abs(sums[i] - sums[i - 1]));
	}
  
  return minAbsSum;
}

console.log(solution([2, -4, 6, -3, 9]))
console.log(solution([10, 10, 10, 10, 10, -50]))

edited Nov 13, 2019 at 4:31

HCSF

2,7111 gold badge22 silver badges48 bronze badges

answered Aug 29, 2018 at 15:07

juvian

16.1k2 gold badges42 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Anand Dev Singh Over a year ago

Thank you so much for your efforts. I would like to update you that I've taken the test again with your solution and its correctness is 80% and performance is 83% and it was enough to score the passing marks. Thanks again you rock.

Nick Over a year ago

That's it right there. Quick question: if my JS docs are correct, then for sum.sort(), "If omitted, the elements are sorted in ascending, ASCII character order", so sorting [0,3,6,9,13,18] that way gives me [0.13,18,3,6,9], which makes sense given the ASCII premise. Shouldn't a compare function be supplied in the sorting step?

juvian Over a year ago

@Nick thats for strings, these are numbers so it sorting it as it should. I don't remember if this is not in the specification, might just be a browser implementation to sort as numbers if the array has numbers

Collectives™ on Stack Overflow

Find absolute sum of minimum slice - codility [duplicate]

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related