Monday, February 2, 2015

Day 100, ##, Two Sum III - Data structure design, Factorial Trailing Zeroes

Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false
------------------------------------------
class TwoSum {
public:
 void add(int number) {
     if (dic.find(number) == dic.end()) {
         dic[number] = 1;
     }else {
         dic[number]++;
     }
 }

 bool find(int value) {
     for (auto i = dic.begin(); i != dic.end(); i++) {
         if (dic.find(value - i->first) != dic.end()) {
             if (value == i->first * 2 && i->second == 1) {
                 continue;
             }
             return true;
         }
     }
     
     return false;
 }
private:
    unordered_map<int,int> dic;
};

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
----------------------------------------
class Solution {
public:
    int trailingZeroes(int n) {
        int rt = 0;
        while (n) {
            rt += n / 5;
            n /= 5;
        }
        return rt;
    }
};

No comments:

Post a Comment