Post date: Jul 20, 2013 5:23:53 AM
Problem
There are N(0 to N-1) players each having at Max 'M' (0 to M-1) number of followers. You have to select minimum number of players so that the total followers must be equal to a given number 'K'.
I/P would be like,
first line contain N, M, K followed by N lines containing string of 0 or 1 s.t. for i'th line if j'th char is 1 it means j'th person follows player 'i'
For. eg.
3 6 5
111100
000100
000010
ans=2 ( select 0th and 2nd )
Solution
It is not a optimized solution, but can work.
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find minimum number of players that the total followers equal to K -- Amazon
Created Data : 20-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <iterator>
#include <bitset>
using namespace std;
bool IsFollowersEqualK(vector<int>& indices, vector<string>& players, int M, int K)
{
vector<bool> followers;
for(int i = 0; i < players[indices[0]].size(); ++i){
followers.push_back(players[indices[0]][i] == '1');
}
for(int i = 1; i < indices.size(); ++i){
for(int j = 0; j < players[indices[i]].size(); ++j){
if(players[indices[i]][j] == '1') followers[j] = true;
}
}
int totalFollowers = 0;
for(int i = 0; i < followers.size(); ++ i){
totalFollowers += followers[i];
}
return (totalFollowers == K);
}
bool FindMinFollowersEqualK(vector<string>& players, int M, int K)
{
int N = players.size();
for(int r = 1; r <= N; ++r){
vector<bool> v(N);
fill(v.begin() + r, v.end(), true);
do {
vector<int> combs;
for (int i = 0; i < N; ++i) if (!v[i]) combs.push_back(i);
if(IsFollowersEqualK(combs, players, M, K)){
cout << "The indices are ";
copy(combs.begin(), combs.end(), ostream_iterator<int>(cout, ", "));
cout << "\nThe minimum num is " << combs.size() << endl;
return true;
}
} while (std::next_permutation(v.begin(), v.end()));
}
return false;
}
void DoTest(vector<string>& players, int M, int K)
{
cout << "The players information are" << endl;
for(int i = 0; i < players.size(); ++i){
cout << players[i] << endl;
}
cout << "N = " << players.size();
cout << " M = " << players[0].size();
cout << " K = " << K << endl;
if(!FindMinFollowersEqualK(players, M, K)){
cout << "No combinations found" << endl;
}
cout << "-------------------------------" << endl;
}
int main(int argc, char* argv[])
{
vector<string> players;
players.push_back("1111000");
players.push_back("0001000");
players.push_back("0000100");
players.push_back("0000010");
players.push_back("1000000");
players.push_back("0100000");
players.push_back("0010000");
players.push_back("1100000");
players.push_back("0011000");
players.push_back("0000110");
players.push_back("0000110");
DoTest(players, 7, 1);
DoTest(players, 7, 2);
DoTest(players, 7, 3);
DoTest(players, 7, 4);
DoTest(players, 7, 5);
DoTest(players, 7, 6);
DoTest(players, 7, 7);
return 0;
}
Output
The players information are
1111000
0001000
0000100
0000010
1000000
0100000
0010000
1100000
0011000
0000110
0000110
N = 11 M = 7 K = 1
The indices are 1,
The minimum num is 1
-------------------------------
The players information are
1111000
0001000
0000100
0000010
1000000
0100000
0010000
1100000
0011000
0000110
0000110
N = 11 M = 7 K = 2
The indices are 7,
The minimum num is 1
-------------------------------
The players information are
1111000
0001000
0000100
0000010
1000000
0100000
0010000
1100000
0011000
0000110
0000110
N = 11 M = 7 K = 3
The indices are 1, 7,
The minimum num is 2
-------------------------------
The players information are
1111000
0001000
0000100
0000010
1000000
0100000
0010000
1100000
0011000
0000110
0000110
N = 11 M = 7 K = 4
The indices are 0,
The minimum num is 1
-------------------------------
The players information are
1111000
0001000
0000100
0000010
1000000
0100000
0010000
1100000
0011000
0000110
0000110
N = 11 M = 7 K = 5
The indices are 0, 2,
The minimum num is 2
-------------------------------
The players information are
1111000
0001000
0000100
0000010
1000000
0100000
0010000
1100000
0011000
0000110
0000110
N = 11 M = 7 K = 6
The indices are 0, 9,
The minimum num is 2
-------------------------------
The players information are
1111000
0001000
0000100
0000010
1000000
0100000
0010000
1100000
0011000
0000110
0000110
N = 11 M = 7 K = 7
No combinations found
-------------------------------
Press any key to continue . . .