How to simplify the code so that it is not O(2n) complexity

  var a = 0;
  var list = [1,2,3];
  int sum = list.fold(0, (p, c) => p   c);

  for (var i = 0; a < sum / 2; i  ) {
    a = a   list[i];
    print(list[i].toString());
  }

What this code should do: Find a number that approximately divides the array into equal parts by sum.

CodePudding user response：

So, the task is to find an index, such that the sum of the numbers before the index, and the sum of the numbers after the index, are as close as possible.

If numbers can be negative, then it's not as simple, so let's just ignore that unless necessary.

Then it's fairly simple to be linear, you just need two pointers. Either count the sum from from each end, moving and increasing the smaller sum each time, until the two pointers meet. (And you only really need to remember the difference, not the sums.)

int splitBySum(List<int> numbers) {
  var delta = 0;
  var l = 0;
  var r = numbers.length;
  while (l < r) delta  = delta < 0 ? numbers[l  ] : -numbers[--r];
  return l;
}

Another, more complicated, alternative is to have two pointers starting from the same end, one just counting the sum, the other lagging behind and being incremented only when the sum until there drops below half the total sum.

int splitBySum(List<int> numbers) {
  var total = 0, half = 0;
  var i = 0, j = 0;
  while (i < numbers.length) {
    total  = numbers[i  ];
    while (half * 4   numbers[j] < total * 2) {
      half  = numbers[j  ];
    }
  }
  return j;
}

(The test is complicated because it only adds the next number to half if the result is not further from half the total. It's basically half * 2 number[j] ~/ 2 < total, just without doing division.)

The only thing this approach has going for it is that it works with iterables, not just lists. If you have random access, always use the first apporach.