siddhant3s · September 25, 2011 15:10 · Sep 25, 2011
diff --git a/hotpo.cpp b/hotpo.cpp
@@ -0,0 +1,65 @@
+
+/* Comment next line if your implementation doesn't support TR1
+   It will then use STL's map instead of TR1's unordered_map,
+   thus will be a little slow (map take worst case log(N) access time)
+   If you don't care about memory, the solution can be sped up using arrays
+   instead of std::map
+*/
+#define TR1
+#include <iostream>
+#ifdef TR1
+#include <tr1/unordered_map>
+std::tr1::unordered_map<unsigned int,unsigned int> hopto_lengths;
+std::tr1::unordered_map<unsigned int, unsigned int>::iterator it;
+#else
+#include <map>
+std::map<unsigned int,unsigned int> hopto_lengths;
+std::map<unsigned int, unsigned int>::iterator it;
+#endif
+
+unsigned int hotpo_len(unsigned int n, unsigned int currlen = 1)
+{ 
+  if (n==1) return currlen;
+  it = hopto_lengths.find(n);
+  if (it != hopto_lengths.end())
+    return it->second+currlen;
+  else
+    {
+      //      std::cout<<"Calculating hotpo_len("<<n<<")\n";
+      unsigned int result;
+      if(!(n%2))
+	result = hotpo_len(n/2,currlen+1);
+      else
+	result = hotpo_len(3*n+1,currlen+1);
+      hopto_lengths[n] = result - currlen;
+      return result;
+    }
+}
+unsigned int max_hotpo(unsigned int i, unsigned int j)
+{
+  unsigned int max = hotpo_len(i);
+  if (i >j)
+    {
+      return max_hotpo(j,i);
+    }
+  while ( ++i <= j )
+    { 
+      unsigned int curr = hotpo_len(i);
+      // std::cout<<"i="<<i<<" hotpo(i)="<<curr<<std::endl;
+      if(curr > max)
+	max=curr;
+    }
+  return max;
+}
+
+
+int main()
+{
+  unsigned int i,j,r;
+  while(std::cin>>i>>j)
+    {
+      std::cout<<i<<" "<<j<<" "<< max_hotpo(i,j)<<'\n';
+    }
+
+}
+