Manasa and Stones Hacker Rank Solution in C

 https://www.hackerrank.com/challenges/manasa-and-stones/

Below is the explanation given by user Connor Rowe in hacker rank

The key to solving this quickly is to realize that any permutation of moves containing the same amount of "a" and "b" will have the same end result. From this, we know that n stones will have n possible distinct results.

For example, if n is 4, then we have possible results:

0 + a + a + a

0 + a + a + b

0 + a + b + b

0 + b + b + b

We can use this pattern to reduce the problem to a simple O(n) loop, and we must handle keeping elements ordered and avoiding duplicates.

#include<stdio.h>

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,a,b,sum,h[1000000]={0};

        scanf("%d%d%d",&n,&a,&b);

        for(int i=0;i<n;i++)

        {

            sum= i*a+(n-i-1)*b;

            h[sum]++;

        }

        for(int i=0;i < 1000000;i++)

            if(h[i] != 0)

                printf("%d ",i);

        printf("\n");

    }

}