Find number of subsets with given average in C

Question

1.00/5 (2 votes)

See more:

given n unique numbers and want to find number of subsets of them which average of the subsets be divisible by another given number.

What I have tried:

I searched for an algorithm and unfortunately just find
Data Structures and Algorithm: Find a subset with given average[^]
which is written in java language and I can't understand it.
can someone show me implementation of this algorithm in c ? or explain it some more please.

Posted 22-May-18 7:12am

Member 13606974

Updated 22-May-18 8:53am

Add a Solution

Comments

Richard MacCutchan 22-May-18 14:36pm

Try thinking about the problem for yourself. Write down some numbers and think how you could group them so that they could be near to a common average.

Rick York 22-May-18 16:38pm

Here are some things to consider. I will assume you know to find the average of some numbers and how to check divisibility. If not, you need to figure those out first. The next thing is figuring out how to find a subset. That is probably the trickiest aspect of the problem. The link you posted shows one way and that code can be transformed into C fairly easily. Since you don't understand it then you should try an alternative. Look for code to find permutations and combinations. Those are how a subset is usually determined. There are several ways. The way I sometimes do it is a brute force method and works OK when you have less than 64 elements in the set. I "map" each item to a bit and then increment up to the binary limit of that many items. If a bit is on then that means that item is a member of that particular subset. As an example, let's say there are four items in a set. The count will range from 0 to 15 (two to the fourth power minus one). When the step counter is at five the binary value is 0101 so that means items 2 and 0 are in the subset. This is not a particularly efficient method but it works fairly well with small sets, those with less than 64 items.

Member 13606974 23-May-18 3:01am

oh god thanks, sorry I'm not native and may that's why I can't understand algorithm in the above link so tried to learn that by it's code which was java and again I wasn't familiar with java but your help make sense I'll try that out.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2018-05-22T08:08:00

We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think!
And "doing it yourself" doesn't mean "finding the code on the internet" - the link you reference explains the algorithm quite well, along with presenting the Java code to do it. Ignore the code, and put some effort into understanding how the algorithm works instead.
Or better, do it manually on paper, and write down how you did it. That could form teh basis for an algorithm you do understand.

If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!

Patrice T · Answer 2 · 2018-05-22T08:54:00

Quote:
can someone show me implementation of this algorithm in c ? or explain it some more please.

You are learning !
Do try to find the most efficient algorithm on internet.
As a learner, your task is to device an algorithm that do the job. It is by searching the algorithm yourself that you will learn something.
It is better to find a slow algorithm that you understand, rather than a dast algorithm that you don't understand.
You need to find every subset and calc the mean. Take a sheet of paper and a pencil and solve the problem by hand. Het a small set of values and write every possible subset, and think at how you can enumerate them by program.

We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
Any failure of you will help you to learn what works and what don't, it is called 'trial and error' learning.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

Find number of subsets with given average in C

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0