Krishna K Tiwari
BAN USERI like to code and solve mathematical problems. Feel free to catch me for any logical discussion.
Build k max heap will work.
Every time a new element comes add it to k max heap if required.
K max heap will maintain K largest element at a give time.
We can do it in O(n) but not less than that because you need to at least traverse all the node before taking decision.
O(n) solution : Do inorder traversal of binary tree if it in ascending order then tree is BST
I am assuming input is SET and SET contains unique elements.
Nitin : You are correct Integer Overflow condition can come.
My mistake.
- Krishna K Tiwari March 20, 2013package algo;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class MissingElement {
public static void TwoMissingElements(Set<Integer>numbers){
double x=0,y=0;
double p=0;
double q=1;
int sum1=55;
int sum2=0;
Iterator itr = numbers.iterator();
while(itr.hasNext()){
sum2 = sum2 + (int)itr.next();
}
p = sum1-sum2;
System.out.println("P "+p);
itr = numbers.iterator();
while(itr.hasNext()){
q = q * (int)itr.next();
}
q=3628800/q;
System.out.println("Q "+q);
double k = Math.pow(p, 2.0);
x = p + Math.pow(k-4*q, 0.5);
x=x/2;
y =p-x;
System.out.println("First Element :"+x+ " Second Element :"+y);
}
public static int OneMissingElement(Set<Integer>numbers){
/*
* sum1 will represents sum of 1 to 10 that is fixed. n*(n+1)/2
* n=10 so sum1 = 55
*/
int sum1=55;
int sum2=0;
Iterator itr = numbers.iterator();
while(itr.hasNext()){
sum2 = sum2 + (int)itr.next();
}
return sum1-sum2;
}
public static void main(String args[]){
Set<Integer> numbers= new HashSet<Integer>();
for(int i=1;i<=10;i++){
if(i==4||i==6)
continue;
numbers.add(i);
}
MissingElement.TwoMissingElements(numbers);
//System.out.println(MissingElement.OneMissingElement(numbers));
}
}
Key : SET contains unique elements.
Case : Only one number is missing.
Missing number = sum {1 to 10} - sum{set elements}
Case : Two numbers are missing assume them X and Y.
X+ Y = sum {1 to 10} - sum{set elements}
X*Y = mul (1 to 10 ) / mul (set elements)
Will post the code in few minutes.
Actually 20 is not producible from 2^i or 5^j.
- Krishna K Tiwari March 20, 2013Question says we need to print N numbers.
Every step compare 2^i with 5^j and print the minimum. In every step increment i and j based on what you have used in that step.
package algo;
public class PrintN {
public static void printN(int N){
int count =0;
int num1=1;
int num2=1;
while(count <N){
int k=num1*2;
int l=num2*5;
if(k<l){
System.out.print(k+" ");
num1=num1*2;
}else{
num2=num2*5;
System.out.print(num2+" ");
}
count++;
}
}
public static void main(String args[]){
PrintN.printN(10);
}
}
RepBhrisBrown, Animator at Achieve Internet
I teach the art of cooking, including food preparation, various cuisines, and techniques of cooking. I work at colleges and ...
HEAP
- Krishna K Tiwari April 03, 2013