CareerCup

/* Of course use StringBuilder instead of just String. Accidentally implemented turning int into String also :D
*/


public class BinaryStringSum {




public static void main(String[] args) {

System.out.println(Integer.valueOf(intToString(32623634),2));
System.out.println(Integer.valueOf(intToString(43442642),2));

System.out.println(Integer.valueOf(binaryStringSum(46263, 43734),2));
System.out.println(46263+43734);


}


public static String binaryStringSum(int a, int b) {

String bS , aS, res = "";
bS = intToString(b);
aS = intToString(a);

int i = bS.length() > aS.length() ? bS.length()-1 : aS.length()-1, c = 0;
while(i >= 0) {
int bit1 = aS.length() > i ? aS.charAt(i) - '0' : 0;
int bit2 = bS.length() > i ? bS.charAt(i) - '0' : 0;
int sum = bit1 + bit2 + c;
c = (2 & sum) != 0 ? 1 : 0;
res = ((sum & 1) != 0 ? 1 : 0) + res;
i--;
}
if(c == 1) res = 1 + res;

return res;
}

public static String intToString(int num) {

int mask = 1 << 30;
String numS = "";

if(num == 0) return "0";
else {
while((num&mask) == 0) {
mask = mask >> 1;
}
while(mask!=0) {
numS = numS + ((num&mask)!= 0 ? 1 : 0);
mask = mask >> 1;
}
}

return numS;
}

}

Solvable with recursion, start with the whole matrix, check the edges of the rectangle, if an edge contains O, split the matrix into three areas without the O, solve the problem for the 3 smaller areas. DP - keep track of the biggest rectangle found so that the smaller areas that can't contain a bigger rect aren't explored. Dunno if that is optimal though, this is 3^(n*m) with DP, this would be my first try.

I would use a red-black tree the key being the login time, then write an additional function rangeQuery which collects the users. Red black tree because it is balanced and therefore faster. In the rangeQuery function we keep adding till we hit the upper bound, but we have to traverse a part of the left tree as well if the root is greater than the lower bound.

check for every point of the smaller rectangle if it is contained within the bigger rectangle

O(n^2) - char matrix represents the map, count only the bottom right X's of the islands, that is, skip the X's that have right neighbours or if one of the previous neighbouring X's in the row had a bottom neighbour skip all the X's of that island in the row, else islands++.

O(n log n) - choose 2 smallest lengths for joining first - minHeap, put result back to heap, repeat till only one element in heap remains (the final length)