first triangle number to have over five hundred divisors


/*
 * 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?
 */

/**
 * if we get prime factors as p^a * q^b * .... *r^k then the no of factors we
 * get will be (a+1)*(b+1)*...(k+1)
 *
 *
 * eg prime factors of 441 are 3,3,7,7 that is 441 = 3^2 * 7^2 so the no of
 * factors will be (2+1)*(2+1)=3*3=9
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author Umang B Bhatt 
 * bhatt.umang7@gmail.com
 */
class FactorNode
{

    int count; // power
    int no; // the actual number

    @Override
    public int hashCode()
    {
        return no;
    }

    @Override
    public boolean equals(Object obj)
    {
        if (obj == null)
        {
            return false;
        }
        if (getClass() != obj.getClass())
        {
            return false;
        }
        final FactorNode other = (FactorNode) obj;
        if (this.no != other.no)
        {
            return false;
        }
        return true;
    }
}

public class Problem_12
{

    /**
     *
     * @param numbers is the number for which prime factors are to be searched
     * @return will return a list of prime factors for the given number
     */
    public static List<Integer> primeFactors(long numbers)
    {
        long n = numbers;
        List<Integer> factors = new ArrayList<>();
        for (int i = 2; i <= n / i; i++)
        {
            while (n % i == 0)
            {
                factors.add(i);
                n /= i;
            }
        }
        if (n > 1)
        {
            factors.add((int) n);
        }
        return factors;
    }

    /**
     *
     * @param number is the number for which divisors are to be calculated
     * @return HashMap<Integer, FactorNode> containing number and thir power
     */
    public static HashMap<Integer, FactorNode> getFactorsWithPower(long number)
    {
        // maintain how many time a prime fator is repeated
        // that is to know the power
        HashMap<Integer, FactorNode> factorsMap = new HashMap<>();
        for (Integer primeFactor : primeFactors(number))
        {
            FactorNode node = factorsMap.get(primeFactor);
            if (node == null)
            {
                FactorNode newNode = new FactorNode();
                newNode.no = primeFactor;
                newNode.count = 1;
                factorsMap.put(primeFactor, newNode);
            } 
            else
            {
                node.count++;
            }
        }
        return factorsMap;
    }

    /**
     *
     * @param number is the number for which we want to find number of factors
     * @return no of factors of given number
     */
    public static int getDivisorCount(long number)
    {
        int factorCount = 1;

        HashMap<Integer, FactorNode> factorsMap = getFactorsWithPower(number);

        // calculate no of factors
        for (Integer key : factorsMap.keySet())
        {
            factorCount *= (factorsMap.get(key).count + 1);
        }
        return factorCount;
    }

    public static void main(String args[])
    {
        int i = 1;
        int sum = 0;
        primeFactors(441);

        do
        {
            sum += i;
            i++;
        } while (getDivisorCount(sum) < 500);

        System.out.println("Ans is : " + sum);
    }
}