incarose
BAN USERThis will print "all" the pair, without duplicates
O(n^0.5) < O(n)
public static void findSumSquares(int num) {
int n = (int)Math.sqrt(num)/2 + (int)Math.sqrt(num)%2;
for(int i = 0; i <= n; i++){
int asqr = num-(int)Math.pow(i,2);
int a = (int)Math.sqrt(asqr);
if((int)Math.pow(a,2) == asqr)
System.out.println("(+/-)"+a+" (+/-)"+i);
}
}
public static void main(String args[]) {
Trie root = new Trie();
root.addWord("ca");
root.addWord("cat");
root.addWord("caw");
root.addWord("cauw");
root.addWord("cw");
root.addWord("cramtowa");
root.addWord("mccatorw");
Set<String> result = new HashSet<>();
FindWords(root, "c*a*", "", result);
System.out.println(result);
}
private static void FindWords(Trie root, String word, String prefix, Set<String> result){
if(word == null || word.length()==0 || root == null)
return;
StringBuilder sb = new StringBuilder();
Trie current = root;
for(int i=0;i<word.length(); i++){
char c = word.charAt(i);
if(c == '*'){
String w = word.substring(i);
char child = 'a';
for(Trie t: current.childs()){
FindWords(t, w, prefix+sb.toString()+child, result);
child++;
}
}else{
int index = c - 'a';
if(current.childs()[index] != null){
current = current.childs()[index];
sb.append(c);
}else{
return;
}
}
}
if(current.isKey()){
System.out.println("Found String: "+prefix+sb);
result.add(prefix+sb);
}
}
private static int Flip(int[] numbers, int k){
int length = numbers.length;
int currentMax = 0;
int startIndex = 0;
int index = 0;
while(index < length){
index = startIndex;
int zeros = k;
int count = 0;
while(zeros >= 0 && index<length){
if(numbers[index++] == 0 ){
if(zeros == 0) break;
if(zeros == k) startIndex = index;
zeros--;
}
count++;
}
currentMax = Math.max(count, currentMax);
}
return currentMax;
}
class MinimumBreak {
int breaks[];
public int minimumBreaks(Set<String> dic, String word){
breaks = new int[word.length()+1];
for(int i=0;i<breaks.length;i++) breaks[i] = -1;
int result = findBreaks(dic, word, 0);
return result;
}
private int findBreaks(Set<String> dic, String word, int from){
if(dic.contains(word.substring(from))) {
breaks[from] = 0;
}else {
StringBuilder prefix = new StringBuilder(word.length());
int min = Integer.MAX_VALUE;
for (int i = from; i < word.length()-1; i++) {
prefix.append(word.charAt(i));
if (dic.contains(prefix.toString())) {
if (breaks[i + 1] == -1)
breaks[i + 1] = findBreaks(dic, word, i + 1);
min = Math.min(min, breaks[i + 1]+1);
}
}
breaks[from] = min;
}
return breaks[from];
}
}
We can get O(Min(m,n)^2) if we do bit manipulation:
- incarose November 14, 2017For each row ( or column depends M < N or N < M ) we do
( example with rows )
Ri & Rj = Rij
if Rij > 0 menas we have 1's at the same Col.
Now lets check if the number of 1's > 1
if (Rij and (Rij -1)) > 0 ( x & (x-1) removes the right most 1')
we have more than 1 '1' in the row. And we found a rectangle.
This will need a nested loop to check every Ri & Rj ( i< j ) i,j <= Number of rows ( or columns )