bartender
BAN USER- 0of 0 votes
AnswersWhat is the Minimum Amount not possible using an infinite supply of coins (Unbounded knapsack)
- bartender in United States
You are given coins of
Denominations {v1, v2 , v3, v4 ....vn } of weight {w1, w2, w3 .....wn}
Now that you have a bag of capacity W .
Find the smallest Value V that is not possible to have in the bag.
(Note , you are not trying to maximize the value V)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
/* You are given with three sorted arrays ( in ascending order), you are required to find a triplet
( one element from each array) such that distance is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then
distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
Please give a solution in O(n) time complexity
*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 300;
int a[N];
int b[N];
int c[N];
int al, bl, cl;
inline int min(int a, int b, int c)
{
return min(min(a, b), c);
}
inline int dist(int a, int b)
{
return max(a-b, b-a);
}
inline int dist(int a, int b, int c)
{
return max(max(dist(a,b), dist(a,c)), dist(b,c));
}
int main()
{
cin >> al;
for (int i = 0; i < al; i++) cin >> a[i];
cin >> bl;
for (int i = 0; i < bl; i++) cin >> b[i];
cin >> cl;
for (int i = 0; i < cl; i++) cin >> c[i];
int r = dist(a[0], b[0], c[0]);
for (int ai = 0, bi = 0, ci = 0; ai < al && bi < bl && ci < cl;)
{
r = min(r, dist(a[ai], b[bi], c[ci]));
int m = min(a[ai], b[bi], c[ci]);
if (a[ai] - m == 0)
ai++;
else if (b[bi] - m == 0)
bi++;
else
ci++;
}
cout << r << endl;
return 0;
}
/*
input:
2 2 5
2 2 9
1 6
output:
4
input:
10 1 2 3 4 5 6 7 8 9 10
5 2 4 6 8 10
3 -1 13 24
output:
3
input:
10 1 2 3 4 5 6 7 8 9 10
5 2 4 6 8 10
3 1 13 24
output:
1
*/
step 1 . We will maintain pointer to starting point of three array say x,y,z
step 2 . now we need to find minimum and maximum of A[x] , B[y] , C[z]
step 3 . & we know that Max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k])) = difference of (Max - Min) = P ( say.. )
step 4 . As we Need to minimize above value so we need to reduce this difference so we will increment index having minimum value and again perform step 2 .
sum required by using 4 elements = Z
- bartender January 28, 2013Step 1: Find Sum of every 2 elements in a array and store it in array F[].
This takes O(n^2) time as there are n Choose 2 such combinations.
Step2: Also Hash the value of Sum with the two elements that make the sum
<(Sum),(a,b)> such that (a+b)=Sum .This allows for O(1) time retrieval of above calculated sums and the process of hashing will take O(n^2) time and space.Note that there can be more than one combination of <(a,b)> which gives same sum like 2+4=6 and 5+1=6,then we need to store both of them by appropriate modification to your hash table.
Step 3 : sort the array F. This takes time O(n^2 log n)
Step 4: We have to find a,b,c,d such that a+b+c+d=Z
Making groups of two: (a+b)=Z-(c+d); A=Z-B;
A,B are elements of array F[] as each element corresponds to a 2-element sum there and its sorted.So for each element in F[], just find if Z-(that element) is present or not by using the Hash Table.If it is output the pairs <a,b> and <c,d> from Hash Table.
Now we can Look in the Hash Table for A and B to find <a,b,c,d> pairs
Overall Complexity -
O(n^2logn) -Time
O(n^2) -Space