Count And Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer $n$, generate the $n^th$ term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

/**
 * @param {number} n
 * @return {string}
 */

// hash answer
var hash = {};
hash[1] = '1';

var countAndSay = function(n) {
  var hashPos;
  for(var i = n; i >= 1; i--) {
    if (hash[i]) hashPos = i;
  }

  var str = hash[hashPos];
  for(var i = hashPos + 1; i <= n; i++) {
    var _str = '';
    var target = '';
    var num = 0;
    for(var j = 0, len = str.length; j < len; j++) {
      if (target === '') 
        target = str[j], num = 1;
      else if (str[j] === target)
        num++;
      else {
        _str += num + target;
        target = str[j];
        num = 1;
      }
    }

    if (num)
      _str += num + target;
    str = _str;

    hash[i] = str;
  }

  return str;
};

Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between $1$ and $2^h$ nodes inclusive at the last level h.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
  if (!root)
    return 0;

  var depth = 0;

  // find the depth of the tree
  var node = root;
  while (node) {
    depth++;
    node = node.left;
  }

  var minn = 1 << (depth - 1);
  var maxn = (1 << depth) - 1;
  var start = minn;
  var end = maxn;

  // binary search
  while (start <= end) {
    var mid = (start + end) >> 1;
    if (isExisting(mid, minn, maxn, root))
      start = mid + 1;
    else
      end = mid - 1;
  }

  return end;

  function isExisting(num, left, right, node) {
    if (left === right)
      return !!node;
    var tmp = (left + right) >> 1;
    if (num <= tmp)
      return isExisting(num, left, tmp, node.left);
    else
      return isExisting(num, tmp + 1, right, node.right);
  }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
  if (!root)
    return 0;

  var l = findDepth(root.left)
    , r = findDepth(root.right);

  if (l === r)
    return (1 << l) + countNodes(root.right);
  else
    return (1 << r) + countNodes(root.left);

  function findDepth(node) {
    return node ? 1 + findDepth(node.left) : 0;
  }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
  if (!root)
    return 0;

  var ans = 0;

  while (root) {
    var l = findDepth(root.left)
      , r = findDepth(root.right);

    if (l === r) {
      ans += (1 << l);
      root = root.right;
    }
    else {
      ans += (1 << r);
      root = root.left;
    }
  }

  return ans;

  function findDepth(node) {
    var num = 0;
    while (node) {
      num++;
      node = node.left;
    }
    return num;
  }
};

Count Numbers With Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

/**
 * @param {number} n
 * @return {number}
 */
var countNumbersWithUniqueDigits = function(n) {
  if (!n)
    return 1;

  var ans = 0;
  
  for (var i = 1; i <= n; i++) {
    if (i === 1)
      ans += 10;
    else if (i <= 10) {
      ans += A(10, i);
      ans -= A(9, i - 1);
    } else {
      break;
    }
  }

  return ans;
};


function A(a, b) {
  var ans = 1;

  for (var i = a; i >= a - b + 1; i--)
    ans *= i;

  return ans;
}