Geeky Minds

Innovation, Inspiration, Instigation

Oct 16, 2017 - 2 minute read - Comments - Problem Solving Ruby

Solving Project Euler Problem 42 – Coded Triangle Numbers

Following up from my previous post, where I attempted Solving Project Euler Problem 13 – Large Sum, I took up Problem 42 – Coded Triangle Numbers

While the original problem is a bit more complex, Hackerrank had broken it down a bit more simpler.

Note: This solution times out after the first 2 test cases out of a total of 7 test cases. So, while the solution is technically correct, it’s not the most optimal way to go about it.

Problem Statement

The nth term of a sequence of triangle numbers is given by,

tn= 0.5 n (n+1)

So the first ten triangle numbers are:

1,3,6,10,15,21,28,36,45,55,⋯

You are given an integer. If it is a triangular number tn, print the term n corresponding to this number, else print −1

Input Format

First line of input contains an integer T denoting the number of test cases. Each of the next T lines contains an integer.

Output Format

Print the answer corresponding to each test case in a new line.

Constraints

1≤T≤10^5
1≤tn≤10^18

Sample Input #00:

3

2

3

55

Sample Output #00:

-1

2

10

A Rough Solution:

    def find_triangle_term(number)
      flag = 0
      (1..number).each do |num|
        if number == (0.5 * num * (num + 1)).to_i
          flag = num
        else
          flag = 0
        end
        break if flag > 0
      end
      (flag == 0)? -1:flag
    end
    
    
    test_cases = STDIN.readline().chomp.to_i
    loop do
      triangle_number = STDIN.readline().to_i
      puts "#{find_triangle_term(triangle_number)}"
      test_cases = test_cases - 1
      break if test_cases == 0
    end

Breakdown of the solution:

  • Read the number of test cases from STDIN as an integer
  • Loop over the test cases
  • Read the set of numbers (1 on each line, 1 for each test case)
  • Checking each input with the find_triangle_number() function and print the output
    • find_triangle_num() function:
      • Set a flag value
      • Loop from 1 to the entered number, checking if it’s a triangle number or not.
        • Assign the term value to flag if it’s a triangle number
        • Assign 0 to flag if it’s not a triangle number
      • Check flag value and return -1 or the flag value as appropriate

That’s it, folks! I’ll be writing more about other problems I solve as and when they happen 🙂

Note: Solution files for this and any future Project Euler problems that I solve can be found here: Github: glnarayanan/ProjectEuler

Tags: Hackerrank Problem Solving Project Euler Ruby

comments powered by Disqus