# HackerRank: Sherlock and Array

This is the solution for HackerRank with Ruby
This time, I challenged Sherlock and Array.

## Problem

Please check the detail of problem ‘Sherlock And Array’ in HackerRank.

### Sample Input

`231 2 341 2 3 3`

```NO
YES```

## Solution

Here is my solution.
I could not write the correct answer all at once, but gradually improved in order and came up with the answer. Only the code that was judged to be the correct answer will be added.

I think there are many other ways to solve it, so if you have any questions or know better way, please comment via Twitter or Github.

``````def balancedSums(arr)
n = arr.size
x = 0
sum = arr.sum
if n == 1
return 'YES'
else
arr.each do |y|
if 2 * x == sum - y
return 'YES'
end
x += y
end
return 'NO'
end
end``````

### Initial Code

The code I originally wrote was like this:
In this case, passed sample test, but there were some problems such as not being able to satisfy when input has only one element, and timed out when the number of elements increased.

``````def balancedSums(arr)
n = arr.size
i = n - 2
right_all = arr.slice(1..-1).sum
if right_all == 0
result = 'YES'
else
i.times do |j|
if j == i
left_all = arr.slice(1..-1).sum
if left_all == 0
result = 'YES'
break
else
result = 'NO'
end
else
arr_left = arr.slice(0..j)
arr_right =arr.slice(j+2..-1)
if arr_left.sum == arr_right.sum
result = 'YES'
break
else
result = 'NO'
end
end
end
end
return result
end``````

### Tried to change the structure inside of loop

First of all, I tried to improve the structure inside of the loop to speed up and implement it. I tried various trials and errors, such as checking the first and last times of the boundary elements first, and then calculating the others, but the results did not change.

``````def balancedSums(arr)
n = arr.size
i = n - 2
right_all = arr.slice(1..-1).sum
left_all = arr.slice(0..-2).sum
#p right_all
#p left_all
if right_all == 0
result = 'YES'
elsif left_all == 0
result = 'YES'
else
i.times do |j|
if j == i
left_all = arr.slice(1..-1).sum
if left_all == 0
result = 'YES'
break
else
result = 'NO'
end
arr_left = arr.slice(0..j).sum
arr_right = arr.slice(j+2..-1).sum
if arr_left == arr_right
result = 'YES'
break
else
arr_left = arr.slice(0..j)
arr_right =arr.slice(j+2..-1)
if arr_left.sum == arr_right.sum
result = 'YES'
break
else
result = 'NO'
end
result = 'NO'
end
end
end
return result
end``````

### Check “Discussion”

I was thinking “Is it possible to compare the sum of only the difference sets of sequences?”, but I did not come up with a good idea, so I decided to see what kind of discussion is going on regarding timeout in the “Discussion” part in order to get a different way of thinking.

Similarly, among the comments of those who are suffering from timeout, there is such a comment:

Hello friends,
Sherlock and Array hackerrank problem can be solved easily by deriving a linear equation.

According to him, the problem is to use a “linear equation”.

What is a linear equation?
According to Wikipedia…

In mathematics, a linear equation is an equation that may be put in the form

where  are the variables (or unknowns), and  are the coefficients, which are often real numbers.

Quote: Wikipedia

It’s hardly understand this by reading this explanation, but in simple terms it seems to be a linear equation. It seems that this problem can be solved by making some equations such as ax + by = c.

Well, how to actually use this… The explanation to apply explanation above to this problem in this video.

When y is moved in order from the beginning when the total sum is sum, the sum of the left and right arrays of y can be calculated using sum and y, so that is the method to use.

When the conditions are met, the sum of the left and right arrays is expressed as x, and they are as follows.

• sum = arr.sum
• y = arr[i], 0 ≦ i < n
• sum = 2x + y

Since y is moved sequentially from the beginning to the end of the array to check, if x is the sum of the elements on the left side of y, the value of x is 0 at the beginning, but each time y moves, the previous y the value obtained by adding is x.

In this way, I wrote:

``````def balancedSums(arr)
n = arr.size
x = 0
sum = arr.sum
if n == 1
return 'YES'
else
arr.each do |y|
if 2 * x == sum - y
return 'YES'
end
x += y
end
return 'NO'
end
end``````

この考え方でいくと、以下のように書けると思います。

It was quite simple and did not time out any more.

## Impression

This problem took some time.
I think that if I can think of a problem in mathematics, I can think smarter and simpler.