CareerCup

public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
 	int N = input2;
	int K = input3;
	int len = input1.Length;
	if((N < K || K < 1)||(N!=len))
	{
		return  -1;
	}
 	int i = 0;
	int j = 0;
	for(i = 0;i < N;i++)
	{
		if(input1[i] < 1)
		{
			return   -1;
		}
	}
	for(i = 0;i < N;i++)
	{
		for(j = 0;j < N - i - 1;j++)
		{
			if(input1[j] > input1[j + 1])
			{
				int temp = 0;
				temp = input1[j + 1];
				input1[j + 1] = input1[j];
				input1[j] = temp;
			}
		}
	}

int Out = 0;
int Val = input1[K-1];
int ValPrev = 0;
for(i = 0;i < K - 1;i++)
{
	if(input1[i] < Val)
	{
		Out += (input1[i] - ValPrev)*(N - i);
		ValPrev = input1[i];
	}
	else if((input1[i] == Val))
	{
		Out += input1[i] - ValPrev;
	}
}
for(i = K;i < N;i++)
{
	if(input1[i] > input1[K-1])
	{
		Out += input1[K-1] - ValPrev;
	}
}
Out += input1[K - 1] - ValPrev;

return Out;
}

We are dealing with worst case. Or put another way we are going to make things difficult for the poor crow and it is not smart enough to figure out that we are being mean.
Let's assume the overflow numbers are all different. (this might also work if some are the same) .
We sort the pots such that the crow starts with the one that needs the most (poor crow )
He knows (this crow just happens to me male) the values so he will try to optimize things.
To find the first one the crow puts the smallest number of rocks in to each pot.
Let O[1] be the number of rocks needed to overflow the pot that needs the least and O[n] be the number that needs the most with O[i] being some pot in between. As we are being mean the crow starts with O[n] and after depositing O[1] in each gets to pot 1 and it over flows.
He has used n*O[1] rocks.
Now all the other pots have O[1] rocks in them so it will take O[2]-O[1] rocks to overflow pot 2.
Now the crow starts at pot n and puts O[2]-O[1] in each but he can stop at pot 2 as pot 1 is out of consideration.
This costs
(n-1) *( O[2]-O[1])
The next round costs
(n-2) *(O[3]-O[2])
And so on
(n-3)*(O[4] - O[3])
n*O[1] + (n-1) *( O[2]-O[1]) + (n-2) *(O[3]-O[2]) + (n-3)*(O[4] - O[3]) …… (n-k)(O[k]-O[k-1])
This is not all that fun to think about another way is to think about how things look when he has made k pots over flow.
The K smallest have been filled and the rest of have had O[k] added to them without result.
Just to make it easier lets rearrange the pots now with the smallest first.
So we can say that we get sum of O[1 to k inclusive] + (n-k) * O[k];
A smart crow which you are not allowed to have being the worst case might begin to see a pattern and suspect you have sorted things to make his life difficult and start working from the other end but we are analyzing the worst case so this is not allowed.
A stochastic crow (they are not found in this part of the country but we had them back east) would use different orders each time and get better results but this gives you the average case not the worst case and is much harder to calculate.

I didn't understand what algorithm to find here. You have the overflow numbers so you need to test it with each pot, with minimum first as you did in the example.

Sort the Overflow array. Worst case is : Overflow[0]*n. For the second overflow you will do (Overflow[1]-Overflow[0])*(n-1) in worst case as every pot has Overflow[0] rocks from last phase. If we continue this "k" times, we are done.

the algorithm should be to create a min heap of k size with all the pots in that and the heapify to be done based on the overflow number. In this way, after creating the heap all one has to do is pop the first element and print the number of stones needed to overflow it.

You need to create a min heap of k size which will take O(n) and then after heap creation just pop all elements one by one and add the total number of stones needed to overflow each pot.

I didnt understand the example,

"Let say two pots are there with overflow no.s {5,58}, and crow has to overflow one pot(k=1). So crow will put 5 stones in pot with overflow no.(58), it will not overflow, then he will put in pot with overflow no.(5), hence the total no. of stones to make overflow one pot is=10."

Why do you have put in (58) first and then in (5). Why not just in (5)

I am assuming that array is Sorted. Have a try

public static void main(String[] args)
{
int[] overflow = {5,8,10,15,17};
int n = 5;
int k = 3;
int result = 0;

for(int i=0 ; i<k ;i++)
{
int min = overflow[i];
for(int j=i; j<overflow.length; j++)
{
overflow[j] = overflow[j] - min;
result = result + min;
}
}

System.out.println(result);
}

I am assuming that the Array is Sorted.

public static void main(String[] args)
{
int[] overflow = {5,8,10,15,17};
int n = 5;
int k = 3;
int result = 0;

for(int i=0 ; i<k ;i++)
{
int min = overflow[i];
for(int j=i; j<overflow.length; j++)
{
overflow[j] = overflow[j] - min;
result = result + min;
}
}

System.out.println(result);
}

I am assuming that the Array is Sorted.

public static void main(String[] args) 
	{
		int[] overflow = {5,8,10,15,17};
		int n = 5;
		int k = 3;
		int result = 0;
		
		for(int i=0 ; i<k ;i++)
		{
			int min = overflow[i];
			for(int j=i; j<overflow.length; j++)
			{
				overflow[j] = overflow[j] - min;
				result = result + min;
			}
		}
		
		System.out.println(result);
}

static int ThirstyCrowProblem(int[] input1, int input2)
{
int len = input1.Length;
int minStones = 0;
Array.Sort(input1);
if (input1 == null || input2 <= 0 || input2 > len || len <= 0)
{
return -1;
}
if(input2 == 1 && input1[0] != 0)
{
minStones = len * (input1[0]);
return minStones;
}
int strt = 0;
for (int i = 0; i < input2; i++)
{
if(input1[i] == 0)
{
strt++;

}
}
int s = 0; minStones = (len-strt) * (input1[strt]); int j = 0;
for (int i = strt; i < input2; i++)
{
if(i>strt)
{
//s = s + input1[i - 1]; j = j+input1[i] - s;
minStones = minStones + Math.Abs(input1[i] - input1[i-1]) * (len - i);
}
}
return minStones;
}

x

Just sort the overflow array and return the sum of first K elements.