<p>Convert a non-negative integer <code>num</code> to its English words representation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = 123
<strong>Output:</strong> &quot;One Hundred Twenty Three&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = 12345
<strong>Output:</strong> &quot;Twelve Thousand Three Hundred Forty Five&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = 1234567
<strong>Output:</strong> &quot;One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= num &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {
private:
void parseDigits(std::string& result, int digit)
{
  switch(digit)
  {
  case 1:
    result += " One";
    break;
  case 2:
    result += " Two";
    break;
  case 3:
    result += " Three";
    break;
  case 4:
    result += " Four";
    break;
  case 5:
    result += " Five";
    break;
  case 6:
    result += " Six";
    break;
  case 7:
    result += " Seven";
    break;
  case 8:
    result += " Eight";
    break;
  case 9:
    result += " Nine";
    break;
  }
}

void parseHundreds(std::string& result, int num)
{
  if (num == 0)
  {
    return;
  }

  int hundreds = num / 100;
  int offset;
  if (hundreds != 0)
  {
    offset = num - (hundreds * 100);
    parseDigits(result, hundreds);
    result += " Hundred";
  }
  else
  {
    offset = num;
  }

  switch (offset)
  {
    case 10:
      result += " Ten";
      break;
    case 11:
      result += " Eleven";
      break;
    case 12:
      result += " Twelve";
      break;
    case 13:
      result += " Thirteen";
      break;
    case 14:
      result += " Fourteen";
      break;
    case 15:
      result += " Fifteen";
      break;
    case 16:
      result += " Sixteen";
      break;
    case 17:
      result += " Seventeen";
      break;
    case 18:
      result += " Eighteen";
      break;
    case 19:
      result += " Nineteen";
      break;
    default:
      int digit;
      if (offset >= 90)
      {
        result += " Ninety";
        digit = offset - 90;
      }
      else if (offset >= 80)
      {
        result += " Eighty";
        digit = offset - 80;
      }
      else if (offset >= 70)
      {
        result += " Seventy";
        digit = offset - 70;
      }
      else if (offset >= 60)
      {
        result += " Sixty";
        digit = offset - 60;
      }
      else if (offset >= 50)
      {
        result += " Fifty";
        digit = offset - 50;
      }
      else if (offset >= 40)
      {
        result += " Forty";
        digit = offset - 40;
      }
      else if (offset >= 30)
      {
        result += " Thirty";
        digit = offset - 30;
      }
      else if (offset >= 20)
      {
        result += " Twenty";
        digit = offset - 20;
      }
      else
      {
        digit = offset;
      }

      parseDigits(result, digit);
      break;
  }
}

public:
    string numberToWords(int num) {
  if (num == 0)
  {
    return std::string("Zero");
  }

  const int ONE_BILLION = 1000000000;
  std::string result;
  int billions = num / ONE_BILLION;
  int offset;
  if (billions != 0)
  {
    parseHundreds(result, billions);
    result += " Billion";
    offset = num - (billions * ONE_BILLION);
  }
  else
  {
    offset = num;
  }

  const int ONE_MILLION = 1000000;
  int millions = offset / ONE_MILLION;
  if (millions != 0)
  {
    parseHundreds(result, millions);
    result += " Million";
    offset = offset - (millions * ONE_MILLION);
  }

  const int ONE_THOUSAND = 1000;
  int thousands = offset / ONE_THOUSAND;
  if (thousands != 0)
  {
    parseHundreds(result, thousands);
    result += " Thousand";
    offset = offset - (thousands * ONE_THOUSAND);
  }

  parseHundreds(result, offset);

  return result.erase(0, 1);
    }
};
8100