Pumphouse
BAN USERPut it in a binary tree with the first node acting as the root. The longest branch to the right is the longest sub sequence.
Iterate through the array and put values into binary tree. Increase the count for each insertion that passes through a node. O(n)
Traverse the list from the head.right to whatever node has the highest count add that node to an array. O(h)
return array
I'm pretty sure there is a better way but this is what I got. I suspect it can be done in constant time using some relation with cubes. This is n^2
public static void main(String [] args){
printNums(sumOfCubes(1000));
}
static HashSet<Integer> sumOfCubes(int n){
HashSet<Integer> nums = new HashSet<Integer>();
int size = (int) Math.pow((double) n, (double) 1/3);
int first;
int second;
int total;
for(int x = 0; x <= size; x++){
for(int i = 0; i <= size; i++){
first = (int) Math.pow(x, 3);
second = (int) Math.pow(i, 3);
//check value
total = first + second;
if(total < n) nums.add(total);
}
}
return nums;
}
static void printNums(HashSet<Integer> nums){
for(Integer ints : nums){
System.out.println(ints);
}
}
I believe you are counting numbers that are both divisible by 3 and 5 twice
class SumThree{
public static void main(String [] args){
System.out.println(sumThreeFive(9));
System.out.println(sumThreeFive(10));
}
static int sumThreeFive(int n){
int result = 0;
for(int x = 0; x < n; x += 3){
result += x;
}
for(int x = 0; x < n; x += 5){
if( x % 3 != 0){
result += x;
}
}
return result;
}
}
I liked this answer the best
import java.util.ArrayList;
import java.lang.Integer;
import java.util.ArrayDeque;
import java.util.Collections;
import java.lang.StringBuilder;
class Bash{
public static void main( String [] args){
ArrayList<Pair> pairs = new ArrayList<Pair>();
pairs.add(new Pair(4, 8));
pairs.add(new Pair(3, 5));
pairs.add(new Pair(-1, 2));
pairs.add(new Pair(10, 12));
System.out.println(minimizeOverlap(pairs));
}
static String minimizeOverlap(ArrayList<Pair> pairs){
ArrayDeque<Integer> result = new ArrayDeque<Integer>();
if(pairs.size() <= 0) return "[,]";
Collections.sort(pairs);
StringBuilder str = new StringBuilder();
Pair first = pairs.remove(0);
str.append("[" + first.getLow());
int last = first.getHigh();
int next;
int highest = 0;
for(Pair x :pairs){
next = x.getLow();
if(last < next && Math.abs(next - last) > 1){
str.append("," + last + "], [" + next);
last = next;
highest = x.getHigh();
}else{
next = x.getHigh();
if(last < next){
last = next;
}
}
}
str.append("," + highest + "]");
return str.toString();
}
static class Pair implements Comparable<Pair>{
int low;
int high;
Pair(int x, int y){
high = y;
low = x;
}
int getLow(){
return low;
}
int getHigh(){
return high;
}
public String toString(){
return "[" + low + "," + high + "]";
}
public int compareTo(Pair o){
if(low < o.getLow()) return -1;
if(low > o.getLow()) return 1;
return 0;
}
}
}
Each recursinve call checks a more significant bit so the second recurs is checking the second significant bit
- Pumphouse February 26, 2015