[Algorithm] Bitwise AND of Numbers Range

Bitwise AND of Numbers Range

Problem statement

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Solution: Detect bit change

A brutal force way of solving it is O(n), simply loop over the whole range. Clearly we can do better. Note that we are doing an AND operation which means 0 is dominating. So the goal for us would naturally to find whether 0 will occur on specific bit.

How do we determine this?

There are two situations where one specific bit is 0:

1) The bit is 0 at the lower bound or upper bound already
2) The bit will change from 1 to 0 in the range.

First scenario is easy, doing lower bound & upper bound will set 0 on those bits. 

The second scenario can be determined by calculating the transform distance of 1 to 0.

For bit 0: transforming from 1 to 0 takes 1 step.

For bit 1: tranforming from 010 to 100 takes 2 steps: 010 -> 011 -> 100

For bit 2: transforming form 0100 to 1000 takes 4 steps: 0100 -> 0101 -> 0110 -> 0111 -> 1000.

...

Indeed for i^th bit to transform from 1 to 0 takes 2ⁱ steps at most. The upper bound of change is 2ⁱ at i^th bit and if the i^th bit is 0 already it will stay at 0, becausing AND operation.

So we can simply check the difference between the upper and lower bound to see how far it can reach, in other words set all i^th bits to be 0 where 2ⁱ < diff.

Code implementation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: int rangeBitwiseAnd(int m, int n) { long long diff = n - m; long long res = m & n; long long base = 1; while(1) { if (base < diff) { res &= (~base); base <<= 1; } else { break; } } return res; } };

[Alogrithm] Valid Perfect Square

Valid Perfect Square

Problem statement:

Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.

This problem can be solved by solving the square root of the given number. So it comes back to the sqrt(x) implementation.

Souliton 1 : Newton-Raphson Method.

The problem can be rewritten as: Given a function f(x) = x^2 - a, find the x so that f(x) = 0. We can use Newton-Raphson Method to approximate the x.

There's a lot of explanation on  that approach. So I won't explain futher. The following links will provide enough details:

http://www.sosmath.com/calculus/diff/der07/der07.html

https://en.wikipedia.org/wiki/Newton%27s_method

Code Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: bool isPerfectSquare(int num) { float x0 = (float)num/2; while (true) { float x1 = x0 - (x0 * x0 - num) / (2.0 * x0); if (fabs(x1 - x0) < 0.0001) break; x0 = x1; } int x = x0; return (x*x == num); } };

Solution 2: Binrary Search:

One can use binary search to find the answer. There problem with binary search is that sometimes we will not hit the correct answer during the binary searching loop. Under that scenario the lhs and rhs value in the end will be a bound for the correct answer.

So for this problem we just need to check the bound to see wether their square equal to the target number.

(I have problems with the approach in the Sqrt(x) problem, I guess we should pick the lower bound for that case)

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: bool isPerfectSquare(int num) { long long lhs = 1; long long rhs = num; while (lhs < rhs) { long long mid = lhs + (rhs - lhs) / 2; long long square = mid * mid; if (square == num) { return true; } else if (square < num) { lhs = mid+1; } else { rhs = mid-1; } } return (lhs * lhs == num || rhs * rhs == num); } };

[Algorithm] Happy Number

Happy Number

Problem statement:

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: 

Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
  
• 82 + 22 = 68
  
• 62 + 82 = 100
  
• 12 + 02 + 02 = 1
  

Solution 1 : Naive Approach (not bad though) 

For this problem a naive approach will perform this transformation of the number and keep track of visited number in a hashset. If we ever visited this number we break out of the loop and check if the repeating number is 1.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public: bool isHappy(int n) { set<int> history; int curr = n; while (true) { int next = 0; while (curr) { int d = curr%10; next += d * d; curr /= 10; } if (next == 1) return true; if (history.count(next) == 0) { history.insert(next); } else { break; } curr = next; } return false; } };

Solution 2: Loop Detection

Based on the naive approach, we can improve by not using the hashset. Imagine we have all the numbers we come across during the transformation as a linked list. Assume the linked list will have a loop and our goal is to find where the loop overlaps.

For example:

48 -> 80 -> 64 -> 52 -> 29 -> 85 -> 89 -> 145 -> 48

We don't need to find out where the loop starts because if the loop starts with 1 it will stuck at 1, in other words, if we break out of the loop by detected a loop we just need to check wether the number we have is 1 or not.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: bool isHappy(int n) { int slow = next(n); int fast = next(next(n)); while(slow != fast) { slow = next(slow); fast = next(next(fast)); } return (slow == 1); } int next(int n) { int sum = 0; while(n) { sum += pow(n%10, 2); n /= 10; } return sum; } };

[Algorithm] Pow(x, n)

Pow(x, n)


Problem statement:

Implement pow(x, n).



Solution 1: Log method.

We can write the problem statement as y = x^n, so let both sides become log(y) = log(x^n). Then we could have log(y) = nlog(x), futher transformation we could have e^log(y) = y = e^nlog(x).

So we just need to compute e^nlog(x). 


Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: double myPow(double x, int n) { double absx = abs(x); int absn = abs(n); bool neg = false; if (x < 0) { neg = (n % 2 != 0); } bool inverse = (n < 0); double abs_res = std::exp(absn * std::log(absx)); double result = abs_res; if (neg) result = -result; if (abs(result) == 0) return 0.0; if (inverse) result = 1.0 /result; return result; } };





Solution 2: Binary Representation

We know that any decimal number can be expressed as a polynomial of binary numbers. It means x^n can be represented as x^(a0*2^0 + a1*2^1 + a2 * 2^2 + ... + ak * 2^k), where ai can be either 0 or 1. Truely the ai values are just the binrary representation of N.




Given N = 12 as an example, its binary representaion is 1100. So x^12 can be rewritten as x^(2^3 + 2^2), by product of power property this can also be rewritten as x^(2^3) * x^(2^2).




x^(2^i) can be easily obtained as we move along with each bit of N's binary representation. If ith bit of N's binary representation is 1 we need to multiply the current x^(2^i) to the result.




Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: double myPow(double x, int n) { if (n < 0) { x = 1/x; } double result = 1; unsigned int absn = abs(n); while (absn) { if (absn & 0x1) result *= x; x *= x; absn >>= 1; } return result; } };

[Algorithm] Design Twitter

Design a simple twitter

Problem statement:

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:

1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.

Solution 1: Tweet-oriented approach

Time complexity:
follow: O(log(m))
unfollow: O(1)
post: O(log(m))
getNewsFeed: best: O(log(N)), worst O(N)

This solution focuses on more on tweets. All tweets are managed together in a multiset sorted by time created (system timestamp) from earliest to latest. All the users will only keep 3 pieces of information: the users they are following, the users following them, a recent activity timestamp which keeps the timestamp of the tweets they post or the tweets they followed post whichever is latest.

When getting the news feed a binary search will be performed to find the lower bound of the relevant tweet given the recent activity timestamp of the user.

When posting a tweet, the user has to notify all their followers to update the recent activity timestamp.

This approach works well in scenarios where the user activity is very frequent thus rendering us no major gap between user's own recent activity and activities of  those they followed. The worst time complexity could be O(N). The other downside is the "post" will notify all followers which can be as worse as O(m).

Implementation is as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139

class Twitter { public: /** Initialize your data structure here. */ Twitter() { systime = 0; } /** Compose a new tweet. */ void postTweet(int userId, int tweetId) { if (users.count(userId) == 0) { users[userId] = User(userId); } users[userId].tweet(systime, users); tweets.insert(Tweet(systime, userId, tweetId)); systime++; } /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */ vector<int> getNewsFeed(int userId) { vector<int> result; if (users.count(userId) == 0) return result; User& user = users[userId]; Tweet tmp = Tweet(user.getRecentTime(), 0, 0); auto lower = tweets.lower_bound(tmp); for (int i=0; i<10 && lower != tweets.end(); lower++) { if (lower->userId == userId || user.isFollowing(lower->userId)) { result.push_back(lower->tweetId); i++; } } systime++; return result; } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ void follow(int followerId, int followeeId) { if (users.count(followerId) == 0) { users[followerId] = User(followerId); } if (users.count(followeeId) == 0) { users[followeeId] = User(followeeId); } users[followerId].follow(users[followeeId]); systime++; } /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ void unfollow(int followerId, int followeeId) { if (users.count(followerId) == 0) return; if (users.count(followeeId) == 0) return; users[followerId].unfollow(users[followeeId]); systime++; } private: class User; class Tweet; class User { public: inline User() { m_recent = 0; m_prev = 0; userId = -1; } inline User(int uid) { userId = uid; m_recent = 0; m_prev = 0; } inline void follow(User& leader) { if (m_following.count(leader.userId) == 1) return; m_following.insert(leader.userId); m_history.insert(leader.m_recent); leader.m_follower.insert(userId); } inline void unfollow(User& leader) { if (m_following.count(leader.userId) == 0) return; m_following.erase(leader.userId); m_history.erase(leader.m_recent); leader.m_follower.erase(userId); } inline void tweet(int timestamp, unordered_map<int, User>& users) { m_prev = m_recent; m_recent = timestamp; for (int userId : m_follower) { User& user = users[userId]; user.m_history.erase(m_prev); user.m_history.insert(m_recent); } } inline int getRecentTime() { int tmp = m_history.empty() ? m_recent : (*m_history.rbegin()); return max(tmp, m_recent); } inline bool isFollowing(int userId) { return m_following.count(userId) == 1; } int userId; private: unordered_set<int> m_following; unordered_set<int> m_follower; multiset<int> m_history; int m_recent; int m_prev; }; class Tweet { public: Tweet(int t, int uid, int tid) : timestamp(t), userId(uid), tweetId(tid) {}; bool operator<(const Tweet& rhs) const { return (timestamp > rhs.timestamp); } int timestamp; int userId; int tweetId; }; unordered_map<int, User> users; multiset<Tweet> tweets; int systime; };

Solution 2: User-oriented design

Time complexity:
follow: O(1)
unfollow: O(1)
post: O(1)
getNewsFeed: O(mlog(n/m))

This solution seems to be a more natural way of design. This design is user oriented which means the system keeps track of all users and their tweets are managed be the user themselves.

System will keep a map of all users and another map which has <key, value> as <userid, userids they are following> to represent the following relationship.

The follow/unfollow is quite straightforward simply set the user following map with user ids.

The post is also very simple, but keep in mind to incorporate a system timestamp into the tweet and make sure the tweets are ordered by timestamp in descending order.

The getNewsFeed is then a k-way merging of tweets from the user him/herself and all his/her followers. The trick here is to user the iterator of the tweets instead of copying the whole set into the merging process. I introduced a TweetRange class to represent the two iterators of the users' tweet. This is just to make it look more straightforward at first glance. You can also survive with simple an std::pair.

The k-way merging we are using is not strictly a merging because we don't actually merge them. 

We start off with having a prority queue of TweetRanges from user him/herself and his/her followees. Then we start to get the latest among them and move forward the iterator from the TweetRange we pick until we either hit the 10 or there's no more left. And of course once one TweetRange is exhausted we just remove that from the queue. Every time we trying to pick one tweet out of the queue we simply pop out that TweetRange we are looking at, pick up the tweet and push it back in so the next TweetRange we look at will have the latest.

This approach is better than solution 1 in terms of time complexity and also more scalable in architecture in a way that we can partition the users without much hiccups. (Partitioning with solution 1 is not going to be easy since the tweets and users are managed separately)

Implementation as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

class Twitter { public: /** Initialize your data structure here. */ Twitter() { systemTime = 0; } /** Compose a new tweet. */ void postTweet(int userId, int tweetId) { users[userId].insert(Tweet(systemTime++, tweetId)); } /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */ vector<int> getNewsFeed(int userId) { multiset<TweetRange> data; set<Tweet>& self = users[userId]; if (!self.empty()) { data.insert(TweetRange(self.begin(), self.end())); } unordered_set<int>& followees = follows[userId]; for (int f : followees) { set<Tweet>& ft = users[f]; if (!ft.empty()) { data.insert(TweetRange(ft.begin(), ft.end())); } } vector<int> feeds; while (feeds.size() < 10 && !data.empty()) { auto it = data.begin(); TweetRange first = *it; data.erase(it); feeds.push_back(first.front->tweetId); if ((++first.front) != first.end) { data.insert(first); } } return feeds; } /** Follower follows a followee. If the operation is invalid, it should be a no-op. */ void follow(int followerId, int followeeId) { if (followerId == followeeId) return; follows[followerId].insert(followeeId); } /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ void unfollow(int followerId, int followeeId) { if (follows.count(followerId) == 0) return; if (follows[followerId].count(followeeId) == 0) return; follows[followerId].erase(followeeId); } private: class Tweet { public: Tweet(int t, int tid) : timestamp(t), tweetId(tid) {} int timestamp; int tweetId; bool operator<(const Tweet& rhs) const { return (timestamp > rhs.timestamp); } }; class TweetRange { public: TweetRange(set<Tweet>::iterator f, set<Tweet>::iterator e) : front(f), end(e) {}; bool operator<(const TweetRange& rhs) const { return (front->timestamp > rhs.front->timestamp); } set<Tweet>::iterator front; set<Tweet>::iterator end; }; private: unordered_map<int, unordered_set<int> > follows; unordered_map<int, set<Tweet> > users; int systemTime; };

[Algorithm] Largest Number

Largest Number

Problem statement

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution: sorting

This is sort of global optimization problem. If we can find a local solution for optimization we can satisfy the global constraint.

Let's try some scenarios to find out the rules to order those numbers. First we start with simple scenarios.

Given two numbers [x, y] how can we form the largest number, we need to compare whether number xy is greater than yx. This is straightforward enough, then how about 3 numbers [x, y, z]?

Suppose 3 numbers are [3, 30, 34], the largest number is 34330. We can observe that the ordering [34, 3, 30]  follows the rule described for the two number scenarios for each pair of numbers. The local optimization of two numbers could be applied to the global optimization. So if we can keep the order of numbers as to form the largest number between each pair of numbers in the set then we can find the largest number consists of the whole set.

So the solution is to sort the whole set by order of [x, y] where xy > yx for each pair of numbers.

The implementation is the following:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public: string largestNumber(vector<int>& nums) { if (nums.empty()) return ""; sort(nums.begin(), nums.end(), comp); string largest; if (nums[0] == 0) return "0"; for (auto v : nums) { ostringstream ostr; ostr << v; largest += ostr.str(); } return largest; } static inline long long catNum(int lhs, int rhs) { if (rhs == 0) return lhs*10; int tmp = rhs; long long base = 1; while (tmp) { tmp /= 10; base *= 10; } return (lhs*base + rhs); } static bool comp(int a, int b) { long long ab = catNum(a, b); long long ba = catNum(b, a); return (ab > ba); } };

[Algorithm] Majority Elements I & II

Majority Elements:

Problem Statement:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Solution 1: Bit checking

Time complexity: O(32N)Space complexity: O(32) or O(1)

Basic idea is to count occurrence of 1's in specific bit position. Each number is a 32 bit integer and if we look at the binary representation of it we can of course count the number of 1's occurrence in the entire array. Simply loop over the vector and count number of 1's at each 32 bit.

There are two flavors in this solution:

First one is to use the loop of bits as outer loop and use loop of vector as inner loop, and this has space complexity of O(1)

Second one is to use loop of vector as outer loop and use loop of bits as inner loop. This flavor has space complexity of O(32). We can also use score based counting instead of real counting, in other words, when we see 1 in the bit we ++count, else we --count.

Code for second flavor is as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: int majorityElement(vector<int>& nums) { vector<int> scores(32, 0); for (auto v : nums) { unsigned int mask = 0x1; for (int i=0; i<32; i++) { if (mask & v) { scores[i]++; } else { scores[i]--; } mask <<= 1; } } int result = 0; for (int i=0; i<32; i++) { if (scores[i] > 0) { result |= (1 << i); } } return result; } };

Solution 2: Championship solution

Time complexity: O(N)

Space complexity: O(1)

Time complexity of O(32n) of solution 1 is a bit annoying the constant factor is too big. Can we have something better, like O(n). The answer is yes.


In fact we can have a championship based solution. Imagine the majority means one number has occurrence of n/2 + 1 at least. And the count of others is n/2 at most. This leads to our championship based solution. We iterate over the vector, and for each number:

If there's no current champion, we make it our champion and set the score to be 1.
If there's one champion, we check:

        If the champion is the same as the value, we increment the score
        else we decrement the score and if the score reaches 0, we dethrone the champion


Finally we will have one champion left and that is our answer.

The code implemented as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int majorityElement(vector<int>& nums) { vector<pair<int, int> > scoreboard; for (auto v : nums) { if (scoreboard.empty()) { scoreboard.push_back(pair<int, int>(v, 1)); } else { pair<int, int>& champ = scoreboard.back(); if (champ.first == v) { champ.second++; } else { champ.second--; if (champ.second == 0) { scoreboard.pop_back(); } } } } return scoreboard.back().first; } };

Majority Elements II:

Problem description:

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

This is a variation of Majority Elements, this time we are asked to first elements occurring more than n/3 times. First off, let's think about how many elements occurring more than n/3 we will have at most.

The answer is 2. We can proof by contradiction:

Element One's occurrence: n/3 + 1Element Two's occurrence: n/3 + 1

If there's another element with occurrence n/3, the total number will be n + 2 which is a contradiction to total number of n.

Solution: Championship based, 2 winners.

Time complexity: O(n) (has a constant factor of 2)

Space complexity: O(1)

The solution is similar to the solution of championship solution. In our case we will have a maximum of two champions and the rules are also the same. We iterate over the vector, if there's slot for a champion, put the number into the winners list and set its score to 1. If there's no slot for a champion either increment the corresponding champion's score if the value is the same or challenge the champion by decrement their score (both of them). If any of the existing champions reaches 0 score, oust them.

Finally we are going to count the winners actual score and decide the majority number.

The code is implemented as following:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

class Solution { public: vector<int> majorityElement(vector<int>& nums) { int n = nums.size(); if (n == 0) return vector<int>(); vector<int> winners; vector<int> points; for (int i=0; i<n; i++) { int val = nums[i]; if (winners.size() == 0) { winners.push_back(val); points.push_back(1); } else if (winners.size() == 1) { if (winners.back() == val) { points.back()++; } else { winners.push_back(val); points.push_back(1); } } else if (winners.size() == 2) { if (winners[0] == val) { points[0]++; } else if (winners[1] == val) { points[1]++; } else { points[0]--; points[1]--; if (points[1] == 0) { points.pop_back(); winners.pop_back(); } if (points[0] == 0) { points.erase(points.begin()); winners.erase(winners.begin()); } } } else { assert(0); } } vector<int> results; for (int i=0; i<winners.size(); i++) { int temp = 0; for (int j=0; j<n; j++) { if (nums[j] == winners[i]) temp++; } if (temp > n/3) results.push_back(winners[i]); } return results; } };

Although we are using the vector here, the maximum we have is just two.