Friday, July 12, 2013

How to Solve Balancing Arrays Problem

Given an array of numbers, return the index at which the array can be balanced by all numbers on the left side add up the sum of all numbers of the right side.

For example:
an array with [1,5,6,7,9,10] can be balanced by splitting the array at position 4
an array with [1, 5, 6, 7, 9, 10] can be balanced by splitting the array at position 4
an array with [3, 8, 4, 15] can be balanced by splitting the array at position 3
an array with [1, 8, 1, 2, 8]) can be balanced by splitting the array at position 3
an array with [1, 3, 5, 1, 2] can't be balanced, hence position -1

package main

import (
    "fmt"
)

func balancingArrays(slice []int) int {
    left := 0
    right := len(slice) - 1
    sumLeft := 0
    sumRight := 0
    for left <= right {
        if sumLeft < sumRight {
            sumLeft += slice[left]
            left++
        } else {
            sumRight += slice[right]
            right--
        }
    }
    if sumLeft == sumRight {
        return left
    }
    return -1
}

func main() {
    fmt.Println(balancingArrays([]int{1, 5, 6, 7, 9, 10})) // 4
    fmt.Println(balancingArrays([]int{3, 8, 4, 15}))       // 3
    fmt.Println(balancingArrays([]int{1, 8, 1, 2, 8}))     // 3
    fmt.Println(balancingArrays([]int{1, 3, 5, 1, 2}))     // -1
}

No comments:

Post a Comment