HackerRankのSherlock and Arrayを解いてみた

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

TOC

Problem
- Sample Input
- Sample Output
Solution
Impression

Problem

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

Sample Input

Sample Output

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.
Quote: https://www.hackerrank.com/challenges/sherlock-and-array/forum/comments/590533

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
$a_{1}x_{1}+\cdots +a_{n}x_{n}+b=0,$
where $x_{1},\ldots ,x_{n}$ are the variables (or unknowns), and $b,a_{1},\ldots ,a_{n}$ 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.

Repeated String HackerRank Solution [Optimal Approach]

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.