Amazon Interview Question
Software EngineersTeam: Development
Country: India
Interview Type: In-Person
Need to modify. for(int i = start; i <= input.length-1-(k-1);i++) to for(int i = start; i <= input.length-k;i++)
Try this
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] integerArray = {1,2,3,4,5,5,6};
System.out.println(getMinStones(integerArray, 3));
}
public static int getMinStones(final int a[], final int k) {
if ((a.length < k)) {
return -1;
}
Arrays.sort(a);
int i, last, stones1, stones2,stones, count;
stones1 = 0;
stones2 = 0;
// Traverse until last repeated value of a[i]
for (i = k; i < a.length && a[k - 1] == a[i]; i++);
last = a[i - 1];
// Count number of stones from end of array
for (i = 0; i < k; i++)
{
stones1 += a[a.length - 1 - i];
}
//
for (i = 0, count = 0; count < k; i++)
{
if ((a[a.length - i - 1] > last) )
{
stones2 += last;
}
else
{
stones2 += a[a.length - i - 1];
count++;
}
}
stones = Math.min(stones1, stones2);
return stones;
}
}
{
import java.util.Arrays;
public class CandidateCode {
public static int ThirstyCrowProblem(int[] input1, int input2, int input3) {
int no_of_pots = input2;
int no_of_pots_overflow = input3;
int temp_var = 0;
// Invalid Input Case
if (input1 == null || no_of_pots_overflow < 0
|| no_of_pots_overflow > input1.length || no_of_pots <= 0
|| input1.length != no_of_pots) {
System.out.println("Control is Here");
return -1;
}
//If Number of OverFlow Pots is Zero
if (0 == no_of_pots_overflow) {
return 0;
}
for (int i = 0; i < no_of_pots; i++) {
if (input1[i] < 0) {
return -1;
}else if (input1[i] == 0) {
if (++temp_var == no_of_pots_overflow) {
return 0;
}
}
}
//Valid Input
Arrays.sort(input1);
int final_array[] = new int[no_of_pots_overflow];
for(int j=0;j<final_array.length;j++){
final_array[j] = input1[j];
}
int n = final_array.length-1;
int min_stones = final_array[n]*(no_of_pots-no_of_pots_overflow+1);
for(int k=0;k<n;k++){
min_stones = min_stones + final_array[k];
}
return min_stones;
}
public static void main(String args[]){
int input1[] = {5,58};
int input2 = 2;
int input3 = 1;
int minStones = ThirstyCrowProblem(input1,input2,input3);
System.out.println("The Minimum Number Of Stones in Worst Case to Overfolw is ::" + minStones);
}
}
}
int ThirstyCrowProblem(int input1[],int input2,int input3)
{
int N = input2;
int K = input3;
if(N < K || K < 1)
{
return -1;
}
int it = 0;
int jt = 0;
for(it=0;it<N;it++)
{
if(input1[it] < 0)
{
return -1;
}
}
for(it=0;it<N;it++)
{
for(jt=0;jt<N-it-1;jt++)
{
if(input1[jt] > input1[jt+1])
{
int temp = 0;
temp = input1[jt+1];
input1[jt+1] = input1[jt];
input1[jt] = temp;
}
}
}
for(it=0;it<N;it++)
{
printf("%d,", input1[it]);
}
int outTemp = 0;
for(it=0;it<K;it++)
{
outTemp += input1[N-it-1];
}
int iVal = input1[K-1];
int iValPrev = 0;
int iOut = 0;
for(it=0;it<K-1;it++)
{
if(input1[it] < iVal)
{
iOut += (input1[it] - iValPrev)*(N-it);
iValPrev = input1[it];
}
else if((input1[it] == iVal))
{
iOut += input1[it] - iValPrev;
}
}
for(it=K;it<N;it++)
{
if(input1[it] > input1[K-1])
{
iOut += input1[K-1] - iValPrev;
}
}
iOut += input1[K-1] - iValPrev;
if(outTemp < iOut)
{
iOut = outTemp;
}
return iOut;
}
This algorithm fails for below case!
Input : {1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,8,11} , K=2, Actual Ans: 8, This Prog Ans: 19 !!!
Algorithm should look at all possibilities and then decide the minimum one
Why is answer 8 in your example, what if the crow put the 8 into the pot with overflow number of 11?
The answer to the question
"Why is answer 8 in your example, what if the crow put the 8 into the pot with overflow number of 11?"
is that the crow is intelligent enough to know that if he puts 2 stones in 4 pots, he would at least overflow 2 pots.
Try this
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] integerArray = {1,2,3,4,5,5,6};
System.out.println(getMinStones(integerArray, 3));
}
public static int getMinStones(final int a[], final int k) {
if ((a.length < k)) {
return -1;
}
Arrays.sort(a);
int i, last, stones1, stones2,stones, count;
stones1 = 0;
stones2 = 0;
// Traverse until last repeated value of a[i]
for (i = k; i < a.length && a[k - 1] == a[i]; i++);
last = a[i - 1];
// Count number of stones from end of array
for (i = 0; i < k; i++)
{
stones1 += a[a.length - 1 - i];
}
//
for (i = 0, count = 0; count < k; i++)
{
if ((a[a.length - i - 1] > last) )
{
stones2 += last;
}
else
{
stones2 += a[a.length - i - 1];
count++;
}
}
stones = Math.min(stones1, stones2);
return stones;
}
}
int ThirstyCrowProblem(int input1[],int input2,int input3)
{
int N = input2;
int K = input3;
if(N < K || K < 1)
{
return -1;
}
int it = 0;
int jt = 0;
for(it=0;it<N;it++)
{
if(input1[it] < 0)
{
return -1;
}
}
for(it=0;it<N;it++)
{
for(jt=0;jt<N-it-1;jt++)
{
if(input1[jt] > input1[jt+1])
{
int temp = 0;
temp = input1[jt+1];
input1[jt+1] = input1[jt];
input1[jt] = temp;
}
}
}
for(it=0;it<N;it++)
{
printf("%d,", input1[it]);
}
int outTemp = 0;
for(it=0;it<K;it++)
{
outTemp += input1[N-it-1];
}
int iVal = input1[K-1];
int iValPrev = 0;
int iOut = 0;
for(it=0;it<K-1;it++)
{
if(input1[it] < iVal)
{
iOut += (input1[it] - iValPrev)*(N-it);
iValPrev = input1[it];
}
else if((input1[it] == iVal))
{
iOut += input1[it] - iValPrev;
}
}
for(it=K;it<N;it++)
{
if(input1[it] > input1[K-1])
{
iOut += input1[K-1] - iValPrev;
}
}
iOut += input1[K-1] - iValPrev;
if(outTemp < iOut)
{
iOut = outTemp;
}
return iOut;
}
public static int getMinStones(final int a[], final int k) {
if ((a.length < k)) {
return -1;
}
Arrays.sort(a);
// approach 1:
final int mid = a[k - 1];
int res1 = (mid * (a.length - k));
for (int i = 0; i < k; i++) {
res1 += a[i];
}
// approach 2
int res2 = 0;
for (int i = a.length - 1; i > (k - 1); i--) {
res2 += a[i];
}
System.out.println("Approach 1 = " + res1 + " Approach 2 = " + res2);
return Math.min(res1, res2);
}
Don't you mean
// approach 2
int res2 = 0;
for (int i = a.length - 1; i > a.length - k - 1; i--) {
i.e. randomly picking k pots and assuming worst case
I think this is the best solution so far - a choice between focusing on one pot at a time assuming it is the worst (vertical approach) and hedging your bets to get all the pots you need overflowing at the same time (horizontal approach).
It's not clear to me however if maybe the choice of approach could be adapted dynamically to produce a better result.
Algorithm fails for the below inputs
input : {2,4,7,7,7,7,7,7,7} , K = 3, Actual Ans: 21 , This algo ans : 42
input : {1,2,6,6,6,6,6,6,6,10} , K = 2, Actual Ans: 16 , This algo ans : 19
input : {1,2,3,3,4,4,6,6,6,11} , K = 2, Actual Ans: 17 , This algo ans : 19
input : {1,2,3,4,5,5,6} , K = 3, Actual Ans: 16 , This algo ans : 18
As you can see, it has a whole lot of failing cases.
Yes, this is due to the silly bug as pointed out by Omri Bashari above. Thanks Omri Bashari for pointing out this bug.
Algorithm fails for the below input
input: {1, 2, 2, 3, 3, 3, 3, 3, 5, 9, 9, 11}, K = 5, Actual Ans: 27. This algo ans: 32
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] integerArray = {1,2,3,4,5,5,6};
System.out.println(getMinStones(integerArray, 3));
}
public static int getMinStones(final int a[], final int k) {
if ((a.length < k)) {
return -1;
}
Arrays.sort(a);
int i, last, stones1, stones2,stones, count;
for (i = k; i < a.length && a[k - 1] == a[i]; i++);
last = a[i - 1];
stones1 = 0;
stones2 = 0;
for (i = 0; i < k; i++)
{
stones1 += a[a.length - 1 - i];
}
for (i = 0, count = 0; count < k; i++)
{
if ((a[a.length - i - 1] > last) )
{
stones2 += last;
}
else
{
stones2 += a[a.length - i - 1];
count++;
}
}
stones = Math.min(stones1, stones2);
return stones;
}
}
Input/Output Specifications Input Specification:
1) A array 0 corresponding to 0-value of N pots {01, 02, On}
2) Number of pots
3) K -value ( number of pots which the crow wants to overflow}
Solution:
1. Sort 0-values
2. Get first K of 0-values from sorted list at 1.
3. MinNumber=Min(K)*(N-K+1) + Min(1)+Min(2)+...+Min(K-1)
where Min(K) - O-value of index K in sorted at 2.
So lets input was:
1) Given 0-values: 23,12,34,45,67,21,7
2) total number of pots is 7
3) Need overflow at least 3 pots
Solutions will be:
1) Sort - 7,12,21,23,34,45,67
2) First 3 values are 7,12,21
3) Min number of stone is 21*(7-3+1)+7+12 = 124
So, all what you need to do is just sort and calculate as above
I think it is not so difficult to prove that it is minimum number.
Input/Output Specifications Input Specification:
1) A array 0 corresponding to 0-value of N pots {01, 02, On}
2) Number of pots
3) K -value ( number of pots which the crow wants to overflow}
Solution:
1. Sort 0-values
2. Get first K of 0-values from sorted list at 1.
3. MinNumber=Min(K)*(N-K+1) + Min(1)+Min(2)+...+Min(K-1)
where Min(K) - O-value of index K in sorted at 2.
So lets input was:
1) Given 0-values: 23,12,34,45,67,21,7
2) total number of pots is 7
3) Need overflow at least 3 pots
Solutions will be:
1) Sort - 7,12,21,23,34,45,67
2) First 3 values are 7,12,21
3) Min number of stone is 21*(7-3+1)+7+12 = 124
So, all what you need to do is just sort and calculate as above
I think it is not so difficult to prove that it is minimum number.
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
/* Worst Case can happen only when the pots are arranged in descending order of their O value and their o value is distinct. Crow starts from first minimum traversing till last and for n number of pots required
* n passes will be required.
*
*/
if (input1 == null || input3 < 0 || input3 > input1.length
|| input2 <= 0 ) {
return -1;
}
Arrays.sort(input1);
int stones = 0;
int min = 0;
int prevMin = 0;
for (int i = 0; i < input3; i++) {
min = input1[i] - prevMin;
stones += input2 * min;
input2--;
prevMin = input1[i];
}
return stones;
}
Whats wrong in this?
I sorted in reverse order and checked for first, second , and third minimum and so on
The answer is a straightforward summation that can be written in a formula like below:
No. of stones = ∑ (N-i)*[ x_i+1 - ∑ ( x_j) ]
First ∑ runs from i=0 to K
Second ∑ runs from j=1 to i
Underscore means subscript, to indicate "i"th value in an array "x".
Logic and formulation:
1. Create an ascending array "x". This is number of stones required to fill all N pots.
2. K is the number of pots crow wants to fill
3. The crow will start with x_1 in all the pots one by one and as it has the "worst luck", will find the correct pot only in the Nth try. So, number of stones required if K=1 is N*K
4. Now the crow knows that it has wasted (N-1)*K in all the wrong pots. So now all the remaining pots required K less stones to overflow. So the array "x" changes, such that all the values will be x_1 less. This is the crucial part. Changing of the array is taken care of in second summation.
5. Now repeat for the next pot from step 3 from second pot with new array.
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] integerArray = {1,2,3,4,5,5,6};
System.out.println(getMinStones(integerArray, 3));
}
public static int getMinStones(final int a[], final int k) {
if ((a.length < k)) {
return -1;
}
Arrays.sort(a);
int i, last, stones1, stones2,stones, count;
for (i = k; i < a.length && a[k - 1] == a[i]; i++);
last = a[i - 1];
stones1 = 0;
stones2 = 0;
for (i = 0; i < k; i++)
{
stones1 += a[a.length - 1 - i];
}
for (i = 0, count = 0; count < k; i++)
{
if ((a[a.length - i - 1] > last) )
{
stones2 += last;
}
else
{
stones2 += a[a.length - i - 1];
count++;
}
}
stones = Math.min(stones1, stones2);
return stones;
}
}
import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}
int result = (input2-input3)*input1[input3-1]+sumval;
return result;
}
else{
return -1;
}
}
}
import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}
int result = (input2-input3)*input1[input3-1]+sumval;
return result;
}
else{
return -1;
}
}
}
import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}
int result = (input2-input3)*input1[input3-1]+sumval;
return result;
}
else{
return -1;
}
}
}
import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}
int result = (input2-input3)*input1[input3-1]+sumval;
return result;
}
else{
return -1;
}
}
}
Guys try this your code will be solved.
function ThirstyCrowProblem(input1,input2,input3)
{
if(input1.length==input2 && input2 >= input3)
{
input1 = input1.sort(function (a, b) {
return a - b;
});
var sumval=0;
for(var i=0;i<input3;i++){
sumval += input1[i];
}
var result = (input2-input3)*input1[input3-1]+sumval;
return result;
}
else{
return -1;
}
}
Hi,
I used the below code:
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;
}
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;
}
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; }
// This is a C++ code, but I do not think it will be a problem
// It covers both scenarios (If the crow wants any pots, or pots with different
// Os
int ThirstyCrowProblem(vector < int > input1, int input2)
{
int size = (int)input1.size();
// It is impossible to have a number of pots that is negative or above the number of all pots
if (input2 > size || input2<1) return -1;
int result = 0;
// We need to know the lowest number of stones
// This means the pots with the least Os
// So, we start by sorting Os, to pick the lowest N (where N is input2)
sort(input1.begin(), input1.end());
int max = input1[input2 - 1];
int lastmax = 0;
for (int t = 1;t<size;t++)
if (input1[t] == input1[t - 1])
input1[t - 1]--;
int skip = 0;
#ifdef HoneyAndMilk
// if what we need is the specific pot (like pots with number 1 have honey while pots with number 2 have milk...)
for (int t = 0;t < size && input1[t] < max;t++) { skip++; result += input1[t]; }
for (int t = skip;t < size;t++) result += max;
#else
// if it is ok to have any pot, and the crow knows that all next left pots are of
// the same O, then it does not need to move back to the first pot in case a smaller
// amount of stones is required to make a closer pot start overflowing
for (skip = size - 1;skip > 0 && input1[skip] >= max;skip--)
result += max;
for (int t = skip;t > skip - input2;t--)
result += input1[t];
#endif
return result;
}
public static int ThirstyCrowProblem(int[] input1, int input2) {
int stones = -1;
if (input2 < 1 || input1 == null || input1.length < 1 || input1.length < input2) {
stones = -1;
} else if ( input1.length == 1) {
stones = input1[0];
} else {
Arrays.sort(input1);
int previous = 0;
stones = 0;
for(int i=0;i<input2;i++) {
stones += (input1[i]-previous) * (input1.length - i);
previous = input1[i];
}
}
return stones;
}
// overflow is k here
sort(array); //ascending order
int lastindex = array.length-1;
int sum = 0;
for(int i=lastindex; i >= lastindex - (overflow - 1); i--)
sum += array[i];
int minsum = sum;
for(int i=lastindex-1; i >= overflow - 1; i--)
{
sum -= array[i+1];
sum += array[i-overflow] + array[i]*(lastindex - i);
if(sum < minsum)
minsum = sum;
}
print(minsum);
#include <iostream>
using namespace std;
void merge(int A[],int l,int h,int m)
{
int mid=(l+h)/2;
int n1=m-l+1;
int n2=h-m;
int X1[n1],X2[n2];
for(int i=0;i<n1;i++)
{
X1[i]=A[l+i];
}
for(int i=0;i<n2;i++)
{
X2[i]=A[m+i+1];
}
int x1=0,x2=0,i=l;
while(x1<n1&&x2<n2)
{
if(X1[x1]<=X2[x2])
{
A[i]=X1[x1];
x1++;
}
else
{
A[i]=X2[x2];
x2++;
}
i++;
}
while(x1<n1)
{
A[i]=X1[x1];
x1++;
i++;
}
while(x2<n2)
{
A[i]=X2[x2];
x2++;
i++;
}
}
void mergesort(int A[],int l,int h)
{
int mid=(h+l)/2;
if(l<h)
{
mergesort(A,l,mid);
mergesort(A,mid+1,h);
merge(A,l,h,mid);
}
}
int main() {
int n,k;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
mergesort(A,0,n-1);
int count;
int ans=32000;
for(count=k;count<=n;count++) /* To check all possibilities*/
{
int i=n-count;
int minvalue=A[i]; /* min among all values in that subarray*/
int sum=0,c=0;
for(;i<n;i++)
{
if(c<k)
{
sum+=A[i];
c++;
}
else
sum+=minvalue;
}
if(ans>sum)
ans=sum;
}
cout<<ans<<endl;
}
#include <iostream>
using namespace std;
void merge(int A[],int l,int h,int m)
{
int mid=(l+h)/2;
int n1=m-l+1;
int n2=h-m;
int X1[n1],X2[n2];
for(int i=0;i<n1;i++)
{
X1[i]=A[l+i];
}
for(int i=0;i<n2;i++)
{
X2[i]=A[m+i+1];
}
int x1=0,x2=0,i=l;
while(x1<n1&&x2<n2)
{
if(X1[x1]<=X2[x2])
{
A[i]=X1[x1];
x1++;
}
else
{
A[i]=X2[x2];
x2++;
}
i++;
}
while(x1<n1)
{
A[i]=X1[x1];
x1++;
i++;
}
while(x2<n2)
{
A[i]=X2[x2];
x2++;
i++;
}
}
void mergesort(int A[],int l,int h)
{
int mid=(h+l)/2;
if(l<h)
{
mergesort(A,l,mid);
mergesort(A,mid+1,h);
merge(A,l,h,mid);
}
}
int main() {
int n,k;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
mergesort(A,0,n-1);
int count;
int ans=32000;
for(count=k;count<=n;count++)
{
int i=n-count;
int minvalue=A[i];
int sum=0,c=0;
for(;i<n;i++)
{
if(c<k)
{
sum+=A[i];
c++;
}
else
sum+=minvalue;
}
if(ans>sum)
ans=sum;
}
cout<<ans<<endl;
}
int ThirstyCrowProblem(int input1[],int input2,int input3)
{
int N = input2;
int K = input3;
if(N < K || K < 1)
{
return -1;
}
int it = 0;
int jt = 0;
for(it=0;it<N;it++)
{
if(input1[it] < 0)
{
return -1;
}
}
for(it=0;it<N;it++)
{
for(jt=0;jt<N-it-1;jt++)
{
if(input1[jt] > input1[jt+1])
{
int temp = 0;
temp = input1[jt+1];
input1[jt+1] = input1[jt];
input1[jt] = temp;
}
}
}
for(it=0;it<N;it++)
{
printf("%d,", input1[it]);
}
int outTemp = 0;
for(it=0;it<K;it++)
{
outTemp += input1[N-it-1];
}
int iVal = input1[K-1];
int iValPrev = 0;
int iOut = 0;
for(it=0;it<K-1;it++)
{
if(input1[it] < iVal)
{
iOut += (input1[it] - iValPrev)*(N-it);
iValPrev = input1[it];
}
else if((input1[it] == iVal))
{
iOut += input1[it] - iValPrev;
}
}
for(it=K;it<N;it++)
{
if(input1[it] > input1[K-1])
{
iOut += input1[K-1] - iValPrev;
}
}
iOut += input1[K-1] - iValPrev;
if(outTemp < iOut)
{
iOut = outTemp;
}
return iOut;
}
Code fails for [3,4,10] with K=2
The program outputs 9 while correct answer is 8.
Greedy approach won't work here
---------------------------------------------
How it would be 8 ?? could you please explain ?
Maybe I'm missing something but I think it's much simpler than the above solutions.
The main observation is to see that the number of stones in each cell after each "round" where a round ends when a pot overflows.
Input: ov = [3, 1, 5]
Let cs = sorted(ov, reverse=True) --> [1, 3, 5]
Round 0: [0, 0, 0]
Round 1: [1, 1, 1] --> first pot overflows
Round 2 :[x, 1+2, 1+2] --> [x, 3, 3] --> second pot overflows
...and so on until all K pots overflow
[c1, c2, c3, ...c_K, c_K, c_K....]
for a total of
sum(cs[:k]) + (N-K) * c[K-1]
The first term is the sum of the stones for the K pots and the remaining are the stones in the partially filled pots.
The runtime is O(N log N) for the sort. :)
Consider this case [3,5,5,5,5,5,5,5,5,5] and the task is to overflow one pot.
If we will start putting 3 stones in each pot then the worst case scenario is 3*10=30. Correct answer is 5.
As mentioned, 0-value is known but information regarding association of 0-value with pots is lost. In that scenarios, how can you rearrange pots (sort) where you do not know the 0-value of pot.
How answer is 5?
Isn't the wost case when crow will find it after using 30 stones instead of 5?
Of course O-value is known, but crow cannot know, so it can start filling each pot with 1 stone at a time. after filling 3 stones in each one overflow will happen and total used stone will be 30 in worst case. How 5 can be answer in this case.
Greedy: Sort the array, and then place the smallest amount of rocks in all pots, 1 will overflow, remove that pot, repeat till k pots overflow.
#include <iostream>
#include <algorithm>
using namespace std;
int const N = 5;
int const k = 3;
int overflow[N] = {5,58,13,7,6};
int main() {
// nlogn sort
sort(overflow, overflow + N);
int rocks = overflow[0] * N;
for (int i = 1; i < k; ++i) {
int potsRemaining = (N - i);
rocks += (overflow[i] - overflow[i-1]) * potsRemaining;
}
cout << "Rocks: " << rocks << endl;
}
The correct algorithm would be to check all possibilities of picking K pots in worst case and picking the one with minimum stones among them. Trying to do the problem with any other algorithm is going to fail as there can be an input formed which would make the algorithm fail.
To check all possibilities, it is actually tweaked program of getting all possible kth subset.
The code goes here. Feel free to challenge with any input.
- asenthilkumargce May 06, 2015