class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n = nums.size(), left = 0, right = n  1;
while (left < right) {
int mid = left + (right  left) / 2;
if (mid % 2 == 0) {
if (nums[mid] == nums[mid1]) right = mid  2;
else if (nums[mid] == nums[mid+1]) left = mid + 2;
else return nums[mid];
}
else {
if (nums[mid] == nums[mid1]) left = mid + 1;
else if (nums[mid] == nums[mid+1]) right = mid  1;
}
}
return nums[left];
}
};
hellotest
@hellotest
Posts made by hellotest

C++ binary search

RE: Short c++ solution
@chaos28 I agree with you. I think the key is to understand what's the order of iterator in map, ascending or descending? When I change that block to be
for (auto a = tweets[t].rbegin(); a != tweets[t].rend(); ++a) { if (top10.size() > 0 && top10.begin()>first > a>first && top10.size() >= 10) break; top10.insert({a>first, a>second}); if (top10.size() > 10) top10.erase(top10.begin()); }
It passes the OJ.
I believe for the original post, that top10.size() > 10 is not going to happen, however it wont affect the result since we can just add everything into the res map and maintain the size to be 10. It just costs more time.

RE: Classic Coin Change Problem, Java DP 6 Lines
class Solution { public: int change(int amount, vector<int>& coins) { // DP, time: O(m*n), space: O(m*n) // dp[i][j]: number of ways to get amount=i using the first j+1 coins // idea: to compute dp[i][j], consider two cases: 1. include coins[j] 2. does no include coins[j] int n = coins.size(); if (n == 0) return 1; int dp[amount+1][n]; for (int j = 0; j < n; ++j) { dp[0][j] = 1; } for (int i = 1; i <= amount; ++i) { for (int j = 0; j < n; ++j) { dp[i][j] = (i >= coins[j] ? dp[i  coins[j]][j] : 0) + (j >= 1 ? dp[i][j1] : 0); } } return dp[amount][n1]; } };
However, it seems that it cannot pass the OJ for some tests.

RE: Classic Coin Change Problem, Java DP 6 Lines
@piyush121 Then you will need to derive an equivalent formula to update dp which may not be so obvious since you must deal with duplicated cases. You can check #322 for Coin Change 1 where we could easily swap two forloops since there we only compute min. numbers.

RE: C++ AC recursive solution
@serendip A slight modification where avoid using long long.
class Solution { public: int superPow(int a, vector<int>& b) { int res = 1; for (int i = 0; i < b.size(); ++i) { res = myPow(res, 10) * myPow(a, b[i]) % 1337; } return res; } private: int myPow(int x, int n) { if (n == 0) return 1; x %= 1337; int half = myPow(x, n/2); if (n % 2 == 0) return half * half % 1337; else return ((half * half) % 1337) * x % 1337; } };
Similarly, we can use iterative version of myPow. I think the key is that three multiplication is easy to overflow, that's why long long type is required if we did not % 1337 immediately.
class Solution { public: int superPow(int a, vector<int>& b) { int res = 1; for (int i = 0; i < b.size(); ++i) { res = myPow(res, 10) * myPow(a, b[i]) % 1337; } return res; } private: int myPow(int x, int n) { int res = 1; x %= 1337; while (n > 0) { if (n & 1) res = res * x % 1337; n >>= 1; x = x * x % 1337; } return res; } };

RE: O(N),O(NLogN) solutions, both O(1) space
I think the third version is more efficient in time since it utilize more space compared to version 2 which is O(1) space. Essentially, they are the "same", we are just changing the order of two loops. Anyway, as a practice, the following is a c++ implementation. I like to use left < right in whileloop. Finally, just test whether the last number we found is valid or not.
class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int left = 1, right = nums.size(); while (left < right) { int mid = left + ((right  left) >> 1); if (existWindow(nums, mid, s)) right = mid; else left = mid + 1; } return existWindow(nums, right, s) ? right : 0; } bool existWindow(vector<int> &nums, int size, int s) { int sum = 0; for (int i = 0; i < nums.size(); ++i) { if (i >= size) sum = nums[isize]; sum += nums[i]; if (sum >= s) return true; } return false; } };

RE: C++ O(n*target) DP solution with idea sharing, similar to coin change problem
@haruhiku How to solve the general problem? If we have mix of positive and negative numbers, and assume every number can be used once. I know it can be solved by DFS approach. But does DP still work here?

RE: Another explanation and solution
Well, I think this explanation gives the correct answer, however the logic is not natural, since the analysis does not give you a concrete strategy to achieve the goal. It just explains how to come up the "solution" (number of pigs required) from another point of view. Great work, though.

RE: Java Slow/Fast Pointer Solution
@mmangelmm said in Java Slow/Fast Pointer Solution:
yours:
(0 + nums[0]) % 3 + 3 = (2) % 3 + 3 = 2 + 3 = 1mine:
(0 + nums[0] + 3) % 3 = (2 + 3) % 3 = 1Yes, they are the same for this special case. I think the operator % is not mathematical module operator, it should be reminder operator (in c++). Think about it, what's the value of (7) % 3 and (4) % 3 should be?
In my machine, (7) % 3 = 1, and also (4) % 3 = 1. So adding 3, we will always get 2.
What's output of (7) % 3 or (7 + 3) % 3 in your machine? Does it give you 2? 
RE: Java Slow/Fast Pointer Solution
@mmangelmm Yes, it's AC. But it does not work for me whenever the input is [2, 3, 9]. when i = 2, the next index I got is 1. Indeed it should be 2. I think % behaves differently for different machine?