Click here to Skip to main content
14,173,097 members
Rate this:
 
Please Sign up or sign in to vote.
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
Updated 22-May-18 8:53am
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.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

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!
   
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 2

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.
   

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

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web02 | 2.8.190524.3 | Last Updated 22 May 2018
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100