I'm writing because I'm trying to solve an algorithm problem and I don't know how to approach it
When there are N coins in the bag, each coin has a value from 1 to M (M > = N). Some coins can have the same value as each other. I took two coins out of this bag, and then I took two coins Record the sum. Explain O(Mlog M) algorithms that can find possible sums that can be made from coins.
Yes> If N=3 and there are 1, 4, and 5 coins in the bag, the total possible is 5, 6, and 9.
I think we can use FFT to get a polynomial, but I'm not sure...
c
I'm not sure about the MlogM algorithm, but this is what I thought of.
There's a better way.
#include <cstdio>
int main(void)
{
int N, M;
scanf("%d %d", &N, &M);
int coin[N] = {0};
intused[M + 1] = {0}; // Check the value of coins that have already been used
int gotsum[M*2 +1] = {0}; // A combination check that has already been obtained....
// You can choose 2 coins of M value, so M*2 + 1
for(int i = 0 ; i < N ; i++)
scanf("%d", &coin[i]);
for(int i = 0 ; i < N-1 ; i++)
{
int first_coin = coin[i];
if(used[first_coin] == 1)
continue;
used[first_coin] = 1;
for(int j = i + 1 ; j < N ; j++)
{
int second_coin = coin[j];
int sum = first_coin + second_coin;
if(gotsum[sum] == 1)
continue;
gotsum[sum] = 1;
printf("sum: %d\n", sum);
}
}
return 0;
}
© 2024 OneMinuteCode. All rights reserved.