VadimM
BAN USERThis can be done with recursion. The only trick is to make sure that the next element of the sum is not greater than the previous (otherwise it will generate duplicates).
public class OddPrinter {
public static void main(String[] args) {
printOdd(8, Integer.MAX_VALUE, "");
}
public static void printOdd(int n, int prevPrint, String s){
for (int i=1;i<=n;i+=2){
if (prevPrint >= i) {
if (n-i == 0) {
System.out.println(s + Integer.toString(i));
} else
printOdd(n-i, i, s + Integer.toString(i) + "+");
}
}
}
}
This problem can be solved in O(n) time.
private static void findPairs(int[] a, int n){
//map of the value of an element to the list of indices of elements equal to this one
Map<Integer, LinkedList<Integer>> indices = new HashMap<Integer,LinkedList<Integer>>();
for (int i=0;i<a.length;i++){
int pair = n-a[i];
if (indices.containsKey(pair) && indices.get(pair).size() > 0){
System.out.println(indices.get(pair).removeFirst() + " " + i);
} else {
if (!indices.containsKey(a[i]))
indices.put(a[i], new LinkedList<Integer>());
indices.get(a[i]).add(i);
}
}
}
An interesting problem. Can be solved by recursion.
public static void main(String[] args) {
String s = "(00)";
System.out.println(find_dept(s,0,s.length()-1));
}
private static int find_dept(String s, int startIndex, int endIndex){
int split = getSplit(s,startIndex + 1, endIndex-1);
if (s.charAt(startIndex) == '(' && s.charAt(endIndex) == ')' && split > -1
&& (s.charAt(startIndex + 1) == '(' || s.charAt(startIndex + 1) == '0')
&& (s.charAt(endIndex - 1) == ')' || s.charAt(endIndex - 1) == '0')
&& startIndex < endIndex-2)
return 1 + Math.max(find_dept(s,startIndex+1,split), find_dept(s,split+1,endIndex-1));
else
return -1;
}
/**
* Find a potential for the recursive call
*/
private static int getSplit(String s, int startIndex, int endIndex) {
int c = 0;
int split = -1;
for (int i=startIndex;i<=endIndex;i++) {
if (s.charAt(i) == '(')
c++;
else if (s.charAt(i) == ')')
c--;
if (c == 0) {
split = i;
break;
}
}
return split;
}
Find the 3 equations of the lines and check if the point is on the appropriate side of the lines.
- VadimM April 17, 2012