old_contents: # Time:  O(n)
  # Space: O(1)
  #
  # Given an integer, convert it to a roman numeral.
  # 
  # Input is guaranteed to be within the range from 1 to 3999.
  #
  
  
  class Solution:
      # @return a string
      def intToRoman(self, num):
          numeral_map = {1: "I", 4: "IV", 5: "V", 9: "IX", 10: "X", 40: "XL", 50: "L", 90: "XC", 100: "C", 400: "CD", 500: "D", 900: "CM", 1000: "M"}
          keyset, result = sorted(numeral_map.keys()), ""
          
          while num > 0:
              for key in reversed(keyset):
                  while num / key > 0:
                      num -= key
                      result += numeral_map[key]
                      
          return result
  
  if __name__ == "__main__":
      print Solution().intToRoman(999)
      print Solution().intToRoman(3999)
new_contents: # Time:  O(n)
  # Space: O(1)
  #
  # Given an integer, convert it to a roman numeral.
  # 
  # Input is guaranteed to be within the range from 1 to 3999.
  #
  
  class Solution(object):
      def intToRoman(self, num):
          """
          :type num: int
          :rtype: str
          """
          numeral_map = {1: "I", 4: "IV", 5: "V", 9: "IX", \
                         10: "X", 40: "XL", 50: "L", 90: "XC", \
                         100: "C", 400: "CD", 500: "D", 900: "CM", \
                         1000: "M"}
          keyset, result = sorted(numeral_map.keys()), ""
          
          while num > 0:
              for key in reversed(keyset):
                  while num / key > 0:
                      num -= key
                      result += numeral_map[key]
                      
          return result
  
   
  if __name__ == "__main__":
      print Solution().intToRoman(999)
      print Solution().intToRoman(3999)
  
subject: Update integer-to-roman.py