Did you know that you can navigate the posts by swiping left and right?

Solving Project Euler Problem 12

25 Nov 2016 . category: Technical Interview . Comments
#interview #challenge #coding #java #Project Euler

Today, we will try to go through the Problem 12 taken from Project Euler. So, the interviewer gives you the following problem:

“The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

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

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

OK, now in a coding interview we should never ever immediately jump into coding. We should first clarify any questions if any, and we should never make any assumptions prior to discussing our thoughts with the interviewer. This way, you clear out any misconseptions and you minimize the possibility that your solution is not correct.


import java.lang.Math; 

public class Solution
{
	private static int MIN_FACTORS = 501;
	
	public long solve(){
		int n =1;
		while (true){
			long triangularNumber = (n*(n+1))/2;
			int factors = getNoOfFactors(triangularNumber);
			if (factors >= MIN_FACTORS){
				return triangularNumber;
			}
			n++;
		}
	}
	
	private int getNoOfFactors(long number){
		
		int factors=0;
		double square = Math.sqrt(number);
		
		for (int i=1; i< square; i++){
			if(number%i==0){
				factors++;
			}
		}

		return square*square==number ? factors*2 -1: factors*2;
	}
	
	public static void main(String[] args)
	{
		Solution solver = new Solution();
		System.out.print(solver.solve());
	}
}

Ok, now you have solved the problem. Now what? A few questions for thought:

  1. What is the complexity both in time and space of your solution?
  2. What if I ask you the first triangle number that has more than 1 billion factors? What you would do next?
  3. Describe algorithm to distribute this over N computers.

Me

Want to hang out? Andreas lives in the beautiful and sunny Cyprus, where he works on data-related projects. In his spare time, Andreas likes to enjoy the beautiful world he lives in.