hawkap
BAN USERprivate static String negaBinary(int x) {
StringBuilder sb = new StringBuilder();
while (x != 0) {
int rem = x % -2;
x = x / -2;
if (rem < 0) {
rem += 2;
x += 1;
}
sb.append(rem);
}
return sb.reverse().toString();
}
It is very similar to transforming into 2-base but tricky case is when reminder is negative.
we just have to convert negative reminder into non-negative:
a=b*c + r, so if r <0 then we can do a=b*c + r +b-b=b*(c+1) + (r-b)
in our case b=-2
I'm very sorry for two previous posts. It is an accident. Admins could you Please delete them as they were posted anonymously and I cannot delete them :(
Thank you, I like idea with bit set.
I would suggest some improvements that can improve performance.
steps of algorithm:
1) Build bit set for every word as you did before (O(N*maxlength) which is linear in terms of characters).
2) Build Trie using bitset:
iterate through all bit masks and on every step:
a) traverse trie in a way that you visit only nodes that evaluate as 0 with current i;
if current bit is 0 then go both children 0 and 1
if current bit is 1 then go 0 only
for every leaf node check if you just found new maximum and update it (store length information in leafs)
b) insert current mask into tree
c) store index and max length of original strings in leafs
In the worst case this algo has the same complexity(but with lower constant factor) but it is much better in average and best case. Because you will traverse only nodes where characters are not shared. So complexity will be O(K) where K is max(N,Number of all possible pairs of words without shared characters) so worst case when you have all N(N-1)/2 pairs and non of them shares character with another. But on practice this is possible only when words are short, because with 26 letters alphabet it is hard to get a lot of words without sharing any character :)))
Best and Average case will have linear time performance.
Here is complete implementation:
and of cause you can implement any part of it manually like implementing your own BST or hashtable. This implementation uses standard java HashMap and TreeMap (which is standard java Red-Black tree implementation)
- hawkap January 23, 2016