But why is that the case?
wilchang
@wilchang
Posts made by wilchang

RE: Share my straightforward solution with HashMap, O(N^2)
Great solution! Two notes:

When you find a dis occurring twice or more, you can add it to a multiple occurring key hashset, so you don't need to go over all the keys in the map when you're building the sum, just the keys in the hashset.

Great idea to ignore getting the sqrt of the sum of the squares! I was using a double as my key because I was doing the sqrt and hit a Memory Limit Exceeded error, but once I stopped using sqrt, I no longer needed to use double as my key and could use int, which let me stay within memory bounds.


RE: Python O(N) solution using HashMap.
Could you explain how the last step is O(n)?
Ahh I see it's because there can be at max length of string s occurrences, so you just check H2 for length down to 0. Clever! 
RE: Java O(n) easy to understand solution, easily extended to any times of occurance
@chidong I think either the problem description should be updated to ask for a number not repeated at all compared to every other element repeated three times or the accepted solution to what it is asking for, which is a single number not repeated three times, and every other number repeated three times. The description literally means just one element is not repeated three times.

RE: Java O(n) easy to understand solution, easily extended to any times of occurance
@chidong the problem description is:
Given an array of integers, every element appears three times except for one. Find that single one.
We are to solve the problems by the description acceptance criteria. The single number is the number not repeated three times. In my example of 1,1,1,4,4,4,4,4,4: the "single number" not repeated exactly three times is 4, as 4 is repeated six times and 1 is repeated three times. Single number refers to the element that is repeated not three times. 
RE: Java O(n) easy to understand solution, easily extended to any times of occurance
@chidong try the use case of 1,1,1,4,4,4,4,4,4. Since the bit at the third position (4=100) is repeated as a multiple of three times, it isn't considered since we check sum%=3. Per the description, all elements are repeated 3 times except one, which in this case is 4, repeated six times, a multiple of 3.

RE: Java O(n) easy to understand solution, easily extended to any times of occurance
@chidong This solution relies on the sum of the bits to not be a multiple of 3 because it checks against the remainder of mod3 and if the frequency of the "single" number is a multiple of 3, then the remainder is 0, so the code will not set any bits. It's a great solution given the assumption that the "single" number doesn't occur in a multiple of 3.

Quick O(n) C# solution using mask with explanation/examples
The problem can be boiled down to taking the sum of the first odd frequency and the max even frequency for each other character.
Lets take a look at the following two examples:
Example 1
abccccdd
a:1, b:1, c:4, d:2
longest palindrome is equal to 1+0+4+2
Notice that I ignore the second odd value.Example 2
aaabbcddd
a:3, b:2, c:1, d:3
longest palindrome is equal to 3+2+0+2
Notice that I ignore the second odd value and then trim down 3 to 2.Take note that all odd numbers have 0x1 bit set, so I wanted to create a mask to get the max even value while encompassing all possible values in this solution. A naive mask would be 0xFFFFFFFE, but we are given the max length of the string as being 1010, so we can do better!
To take advantage of the max length of the string being 1,010, we need a bitmask that covers the case where the string has a single one character and 1009 of another character. This case has both odd values.
1010 in binary is 0011 1111 0010
0x3fe in binary is 0011 1111 1110
Now everything is set for implementing the solution!
public int LongestPalindrome(string s) { if(string.IsNullOrEmpty(s)) return 0; int[] frequencies = new int[128]; foreach(var c in s) { frequencies[c]++; } bool oddFound = false; var longestPalindrome = 0; // smallest mask excluding 0x1 that is larger than the max length of str 1010 is 0x3fe var evenMask = 0x3fe; foreach(var frequency in frequencies) { if(!oddFound && (frequency & 1) == 1) { oddFound = true; longestPalindrome += frequency; } else longestPalindrome += frequency & evenMask; } return longestPalindrome; }

RE: C#, the solution beats 100% of C# submissions
dictionary.ContainsValue is an O(n) function. If you sacrifice more space for another hashset, you can cut down on that call.

RE: A good warning to me to use start+(endstart)/2 to avoid overflow
Overflow happens because sums greater than 2^311 but less than 2^321 will be negative. For example, if you added 1 to 2^311, you'd get int32.minvalue, or 2^31. Lets use a smaller example, say an 8bit number, the max signed value you can store is 01111111, which is 127. If you add one, what do you expect to get as a result? It should be 10000000, which is 128. Due to this overflow, your code will likely infinitely loop.
In C# there's a compiler flag (checked) that will throw an exception for overflow/underflow, but the default behavior is the same as java/c++ with "wrapping" or modulo 2^bitcount of your number type.
In case that didn't make sense or you want to learn more, refer to this article to learn more about exactly what number your sum is becoming: http://www.cplusplus.com/articles/DE18T05o/