Balanced Array Index While Summing an Array from Left and Right

Balanced array index while summing an array from left and right

Use std::accumulate and you can do as follows.

#include <iostream>
#include <vector>
#include <numeric>
#include <cstddef>

int balanceIndex(const std::vector<int>& vec)
{
   for(std::size_t index = 0; index< vec.size(); ++index)
   {
      int left_sum = std::accumulate(vec.begin(), vec.begin() + index + 1, 0);
      int right_sum = std::accumulate(vec.begin() + index + 1, vec.end(), 0);
      if(left_sum == right_sum)
         return index;
   }
   return -1;
}

int main()
{
  std::vector<int> a = {5,1,2,2};
  std::vector<int> b = {1,1,1,1,1,1};
  std::vector<int> c = {2,2,2};

  int answer = balanceIndex(c);  //try for vectors b and c
  (answer != -1) ? std::cout<< answer : std::cout << "None\n";

  return 0;
}

UPDATE: Above solution has a time complexity of O(n^2). As @NicoSchertler mentioned in the comment, a O(n) solution could be as follows:

int balanceIndex(const std::vector<int>& vec)
{
   int right_sum = std::accumulate(vec.begin(), vec.end(), 0);
   int left_sum = 0;
   for(std::size_t index = 0; index< vec.size(); ++index)
   {
      right_sum -= vec[index];
      left_sum  += vec[index];
      if(left_sum == right_sum) return index;
   }
   return -1;
}

How do you test whether both sides of an array total the same? | Javascript Algorithm

You have this part:

   let arr1 = arr.slice(0, (arr[i] - 1));
   let arr2 = arr.slice((arr[i] + 1),);

This is incorrect: arr[i]. That is a value, eg in [2,4,6,8,10] arr[3]==8. You want to slice on the index itself:

   let arr1 = arr.slice(0, i - 1);
   let arr2 = arr.slice(i + 1,);

Please note: There is another error in the two lines :) I leave that to you. Hint: you're now slicing two values out of the array instead of one. Perform the following code in your head first, then somewhere where you verify your results.

let arr = [0,1,2,3,4]
let x = 2;
console.log(arr.slice(0, x - 1));
console.log(arr.slice(x + 1,));

Determine whether or not can an array of numbers can be divided into two arrays, with each array holding the same sum of numbers

The two for-loops are for weighing the two parts of the array, to find the array balancing point of an array.

Think of it like this:

You have a empty balance scale, in the first iteration of the outer for loop, i is zero.

It comes to first for loop, here j is 0 and i is 0 i < j is false, so it doesn't enter the first for-loop and it goes into the second for-loop and subtracts all the numbers from sum.

From second iteration onwards of the outer for-loop, it starts entering the first for-loop and
starts adding the elements of the array one-by-one to the sum.

In pictures, it is like starting with an empty balance scale, adding all the elements into the second scale, and moving one by one element to the first scale, like this:

In the end, if the sum is zero, then the array can be balanced, so return true. If the sum isn't 0, it's unbalanced.

The values in the are balanced by the loops like this:

Iteration of outer for loop when i is 0

Loop 2 -> i(0) j(0) Subtract 1, sum is -1

Loop 2 -> i(0) j(1) Subtract 3, sum is -4

Loop 2 -> i(0) j(2) Subtract 2, sum is -6

Loop 2 -> i(0) j(3) Subtract 6, sum is -12

Iteration of outer for loop when i is 1

Loop 1 -> i(1) j(0) Add 1, sum is 1

Loop 2 -> i(1) j(1) Subtract 3, sum is -2

Loop 2 -> i(1) j(2) Subtract 2, sum is -4

Loop 2 -> i(1) j(3) Subtract 6, sum is -10

Iteration of outer for loop when i is 2

Loop 1 -> i(2) j(0) Add 1, sum is 1

Loop 1 -> i(2) j(1) Add 3, sum is 4

Loop 2 -> i(2) j(2) Subtract 2, sum is 2

Loop 2 -> i(2) j(3) Subtract 6, sum is -4

Iteration of outer for loop when i is 3

Loop 1 -> i(3) j(0) Add 1, sum is 1

Loop 1 -> i(3) j(1) Add 3, sum is 4

Loop 1 -> i(3) j(2) Add 2, sum is 6

Loop 2 -> i(3) j(3) Subtract 6, sum is 0

Final result is true, therefore the array can be balanced

Code:

public class Test {

    public static void main(String[] args) {
        int[] test = { 1, 3, 2, 6 };
        System.out.println("\nFinal result is "+canBalance(test));
    }

    public static boolean canBalance(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.println("\nIteration of outer for loop when i is " + i);
            int sum = 0;
            for (int j = 0; j < i; j++){
                sum += nums[j];
                System.out.println("Loop 1 -> i(" +i + ") j("+j + ") Add "+nums[j] + ", sum is "+sum+"       ");
            }
            for (int j = i; j < nums.length; j++){
                sum -= nums[j];
                System.out.println("Loop 2 -> i(" +i + ") j("+j + ") Subtract "+nums[j] + ", sum is "+sum+"       ");
            }
            if (sum == 0)
                return true;
        }
        return false;
    }
}

If you want to allow shuffling between the elements of the array, you can use recursion as follows (comments are self-explanatory)

public class Test {

    public static void main(String[] args) {
        int[] original = { 10, 2, 24, 32 };
        System.out.println(canDivideArray(original));
    }

    private static boolean canDivideArray(int[] originalArray) {
        int total = 0;

        for (int number : originalArray) {
            total += number;
        }

        // check if sum == 2x for any value of x
        if (total % 2 != 0) {
            return false;
        } else {
            // sum of each half array should be x
            total /= 2;
        }
        return isTotal(originalArray, originalArray.length, total);
    }

    private static boolean isTotal(int array[], int n, int total) {
        // successful termination condition
        if (total == 0) {
            return true;
        }
        
        // unsuccessful termination when elements have finished but total is not reached
        if (n == 0 && total != 0){
            return false;
        }

        // When last element is greater than total
        if (array[n - 1] > total)
            return isTotal(array, n - 1, total);

        //check if total can be obtained excluding the last element or including the last element 
        return isTotal(array, n - 1, total - array[n - 1]) || isTotal(array, n - 1, total); 
    }

}

javascript hackerranks sherlock and array performance issue

You could go through the array from both ends in inwards direction using two pointers (indices). Keep a balance, starting with 0, as follows:

When the balance is negative move the left pointer one step to the right while increasing the balance with the value you leave behind. When the balance is positive, move the right pointer one step to the left while decreasing the balance with the value you leave behind.

When the two pointers meet each other, check the balance. If it is zero, you have success.

Here is the algorithm in ES6 code, together with a text area where you can adapt the input according to the required input format:

function hasMiddle(a) {    var balance = 0, i = 0, j = a.length-1;    while (i < j) balance += balance > 0 ? -a[j--] : a[i++];    return !balance;}
// I/O: event handling, parsing input, formatting output
var input = document.querySelector('textarea');var output = document.querySelector('pre');
input.oninput = function() {    var lines = this.value.trim().split(/[\r\n]+/).filter(s => s.trim().length);    // Strip the case count and array element counts:    lines = lines.slice(1).filter( (s, i) => i % 2 );     // Call function for each test case, returning array of booleans:    var results = lines.map( line => hasMiddle(line.match(/\d+/g).map(Number)) );    // Output results    output.textContent = results.map( pos => pos ? 'YES' : 'NO' ).join('\n');}// Evaluate input immediatelyinput.oninput();

Input:<br><textarea style="width:100%; height:120px">2 3 1 2 3
4 1 2 3 3</textarea><pre></pre>