HAPPY NEW YEAR!

What I've done today is Highly divisible triangular number in Rust and Same Tree in JavaScript.

Math

Problem

Highly divisible triangular number

Problem 12 

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?

Solution

It's easy to understand that if prime factorization of $n$ is given by

$$n=p_1^{v_1}p_2^{v_2}...p_k^{v_k}$$

Then the number of positive divisors of $n$ is

$$d(n)=(v_1+1)(v_2+1)...(v_k+1)$$

If you do not get it, check https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html

So just factorize triangle numbers and check if it's answer.

Implementation

extern crate primal;

fn main() {
    let sieve = primal::Sieve::new(14751430);
    let mut ans = 0i64;
    for i in 1i64..10000000i64 {
        ans += i;
        let factors: Vec<(usize, usize)> = match sieve.factor(ans as usize) {
            Ok(v) => v,
            Err(_) => Vec::new(),
        };
        let mut count = 1;
        for factor in factors {
            count *= factor.1 + 1;
        }
        if count > 500 {
            println!("Answer is {}", ans);
            break;
        }
    }
}

Algorithm

Problem

100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true
Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false
Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Solution

I just to lazy to implement it with non-recursive approach. ;P

Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = (p, q) => {
  if(!q||!p) return q===p;
  return isSameTree(p.left,q.left)&&
    isSameTree(p.right,q.right)&&
    q.val===p.val;
};