ovjforu
BAN USERI think it can be easily solved using below trick. for a given set of points say.. (x1,y1), (x2,y2), (x3,y3).... we need to find (mx,my) such that manhattan distance from all points to this is minimized. so we need to minimize,
|x1-mx| + |y1-my| +....
Note : here we are adding only positive numbers so if this is minimum then sum of square is also minimum..
(x1-mx)^2 + (y1-my)^2 + .....
expanding and solving we get...
(x1)^2 + (x2)^2 + ...
(y1)^2 + (y2)^2 + ...
- 2 mx * (x1+x2+x3+...)
- 2 my * (y1+y2+y3+...)
+N * mx^2 + N * my^2
so in short we need to minimize the below term..
- 2 mx * (x1+x2+x3+...)
- 2 my * (y1+y2+y3+...)
+N * mx^2 + N * my^2
which indirectly means first minimize it for x and then for y...
Node nextNode(Node node) {
if ( node == null ) { return null; }
if ( node.right != null ) {
node = node.right;
while ( node.left != null) {
node = node.left;
}
return node;
} else {
if ( node.parent == null) { // for root node parent == null;
return null;
} else if ( node.parent.left == node) { // it is parent's left node.
return node;
} else {
// node is the right child of parent and it has no right child.
Node currNode = node;
while ( node.parent != null ){ // current node is not root
node = node.parent;
if ( node.val > currNode.val) {
return node;
}
}
return null;
}
}
}
There we are not considering one important point..say for example we can prune our search in following scenarios..
if we know that sum of cubes of say ( 001 ) is = 1 and number itself is 1 then there exists no possibility that there will be any armstrong number between 2-9.. so there by we can resume our search from 10 likewise.. for 1-100.. numbers which we will check are
1, 10-13,20-23,30-32,40 only... we indirectly cut short lot of checks ... this approach will help us discard large range of numbers... also we can use an array of size 10 or 9 .. with precomputed cube...in that way we will reduce even common / repetitive cubic operation...
One additional point of performance improvement is.. when we are changing digits say decimal or tenth then we don't want to compute the whole sum again.. we can store it may be simple on stack.. for current digits sequence of >=10, >=100, >=1000, >=10000,>=100000....etc...
please let me know if this makes any sense...
I think the problem is incorrectly stated. given a series of stock prices at an increasing time period find out the maximum profit. i.e. decide whether you will hold /buy/sell at specified time periods.
with this solution for
2,1,3,5,8,7,4,2,5 will be
10 ... buy at (1) and then sell at (8) ..and again buy at (2) and sell at (5).. its a simple DP problem... here is my solution..
import java.util.Scanner;
public class MaximumDPProfit {
/**
* @param args
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int stockPrices[] = new int[N];
for ( int i=0; i<N;i++){
stockPrices[i] = scan.nextInt();
}
int maxProfit[] = new int[N];
for ( int i = N-2; i >=0 ;i--){
for ( int j= i+1; j <N;j++){
if ( stockPrices[j] > stockPrices[i]){
if ( j+1 < N){
if ( (maxProfit[i]) < (maxProfit[j+1] + stockPrices[j] - stockPrices[i] )){
maxProfit[i] = maxProfit[j+1] + stockPrices[j] - stockPrices[i] ;
}
}else{
if ( maxProfit[i] < (stockPrices[j] - stockPrices[i])){
maxProfit[i] = stockPrices[j] - stockPrices[i];
}
}
}else{
if ( maxProfit[i] < maxProfit[j]){
maxProfit[i] = maxProfit[j];
}
}
}
}
System.out.println("maximum profit : "+maxProfit[0]);
}
}
O(N) time complexity....Here is my solution in Java..
import java.util.Scanner;
public class MaximumProfit {
/**
* @param args
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int arr[] = new int[N];
for ( int i=0; i< N; i++){
arr[i] = scan.nextInt();
}
int currMin = arr[0];
int maxProfit = 0;
int buyPriceI = 0, sellPriceI = -1,tBuyPriceI= 0;
for ( int i=1; i<arr.length; i++){
if ( (arr[i]-currMin) > maxProfit ){
buyPriceI = tBuyPriceI;
sellPriceI = i;
maxProfit = arr[i] - currMin;
}
if ( arr[i] < currMin){
tBuyPriceI = i;
currMin = arr[i];
}
}
System.out.println(" max profit = "+maxProfit+" buy = "+arr[buyPriceI]+" "+arr[sellPriceI]);
}
}
It can be done in Log(n) time .... where n = n1*n2*n3 ( total number of elements).. just treat this as a binary search on one dimensional array. where the actual index in the array should be computed as..
i1 = ( i ) / ( N2 *N3)
i2 = [ (i) % ( N2 * N3)]/N2
i3 = [ i ] % N3
below is the implementation in Java....
import java.util.Scanner;
public class ThreeDimensionalMatrix {
/**
* @param args
*/
public static int binarySearch(int arr[][][],int startI, int lastI,int num,int N1,int N2,int N3){
if ( startI == lastI){
if ( arr[(startI/(N2*N3))][(startI%(N2*N3))/N2][startI%N3] == num){
return startI;
}else {
return -1;
}
}else{
int midI = (startI+lastI)/2;
int test = arr[(midI/(N2*N3))][(midI%(N2*N3))/N2][midI%N3];
if ( test == num){
return midI;
}else if ( test > num){
return binarySearch(arr, startI, midI, num, N1, N2, N3);
}else{
return binarySearch(arr, midI+1, lastI, num, N1, N2, N3);
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N1 = scan.nextInt();
int N2 = scan.nextInt();
int N3 = scan.nextInt();
int arr[][][] = new int[N1][N2][N3];
for ( int i=0;i < N1;i++){
for (int j=0; j<N2;j++){
for ( int k=0; k < N3;k++){
arr[i][j][k] = scan.nextInt();
}
}
}
int temp;
while ( (temp = scan.nextInt()) >=0){
if( (temp =binarySearch(arr,0,N1*N2*N3,temp,N1,N2,N3)) >-1){
System.out.println("i = "+(temp/(N2*N3))+" j = "+( (temp%(N2*N3))/N2)+" k = "+(temp%N3));
}else{
System.out.println("element not found");
}
}
}
}
if you are not allowed to make changes in the class file then the ideal solution will be to make sure that in the make file where list is getting compiled add dependancy on array.
For example.
- ovjforu November 05, 2012