Leet code 397. Integer Replacement

Problem Statement could be found @ https://leetcode.com/contest/4/problems/integer-replacement/

Solution:

There are two important points in this problem:
1. A value might be touched upon multiple times hence it is important to memoize the values
2. If the value is the max value of int (2,147,483,647) , then using just int in algo would give wrong value as for odd case 2,147,483,647 would go out integer range. Hence one should use unsigned int

Following is the code

class Solution {
    int max;
    map<unsigned int, int> valMap;
public:
    int algo(unsigned int n){
         if (n == 1)
            return 0;
        if (valMap.count(n) != 0){
            return valMap[n];
        }
        if (n%2 == 0){
            valMap[n] = integerReplacement(n/2) + 1;
            return (valMap[n]);
        }else{
            int plusOne = integerReplacement(n + 1) +1;
            int minusOne = integerReplacement(n-1) + 1;
            if (plusOne < minusOne){
                valMap.insert(pair<unsigned int,int>( n,  (plusOne )));
                return (plusOne );
            }
            else{
                valMap.insert(pair<unsigned int,int> (n, (minusOne )));
                return (minusOne );
            }
               
        }
    }
    int integerReplacement(int n) {
      unsigned int l = n;
      return algo(n);
    }
};