Labels

Project Euler #12: Highly divisible triangular number

Question
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?

Answer : 76576500

Hacker Rank Problem

Solution


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;

public class Solution {
    static int factor(int a){
        int count=0;
        if(a==1){
            return 1;
        }
        for(int i=1;i<Math.ceil(Math.sqrt(a));i++){
            if(a%i==0){
                count+=2;
            }
        }
        if((Math.ceil(Math.sqrt(a)))==Math.floor(Math.sqrt(a))){
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        int arr[] = new int[1001];
        int temp=0,box=0;
        for(int i=1;i<=1000;i++){
            while(temp<=i){
                box++;
                temp=factor(((box)*(box+1))/2);

            }
            arr[i]=((box)*(box+1))/2;
        }
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        while(test-->0){
            int n=sc.nextInt();
            System.out.println(arr[n]);
        }
    }
}
Labels:

Comments

Post a Comment

Popular Posts