+ 4

Name for set of numbers where all sums are different

Can anyone tell me if a set of N numbers where all possible sums are unique has a name? (e.g. {1,2,4} sums are 1, 2, 4, 3, 5, 6, 7 I would like to query if this has already been proposed as a challenge in sololearn

30th Aug 2019, 8:20 AM
bell
bell - avatar
7 odpowiedzi
+ 7
bell yes, while generating subsets along with sum there is good possibilty of duplicate sums, thatiswhy I wrote in my above comment to remove the duplicates. You can store sum for each subset directly into a set to eliminate duplicate values Here is link to lesson for it https://www.sololearn.com/learn/Java/2182/?ref=app From set, you can directly take highest & lowest value after sorting it. Happy coding
31st Aug 2019, 8:10 AM
Gaurav Agrawal
Gaurav Agrawal - avatar
+ 6
You can generate all subsets along with sum of their elements, and then remove duplicate values of sum. probably, a more better approach can be there, I will look for it. For generating subsets in simple way, you can make use of binary.
30th Aug 2019, 9:54 AM
Gaurav Agrawal
Gaurav Agrawal - avatar
+ 1
https://www.sololearn.com/Profile/6305872/?ref=app Thank you for your answer: "For generating subsets in simple way, you can make use of binary" I have looked this up and tried using a binary mask. It is very useful. If the sums contain duplicate values, it is not a valid set (for the algorithm I want).
31st Aug 2019, 7:14 AM
bell
bell - avatar
+ 1
bell the example you provided (1, 2, 4) can be extended to any size with powers of 2.
31st Aug 2019, 7:25 AM
László Ozsvárt
László Ozsvárt - avatar
+ 1
bell if you have a set of N elements then there are 2^N possible ways to sum them. Since you want all of them to be unique, you can't add any of these to the set while keeping the unique sum property. This will cause the set to contain large numbers even when N is small.
31st Aug 2019, 8:25 AM
László Ozsvárt
László Ozsvárt - avatar
0
https://www.sololearn.com/Profile/3429252/?ref=app you are right :-), I needed strings of similar lengths and powers of 2 grow too fast, while 1, 2 and 4 were too small. i have been playing with the code to generate such numbers. it might make a nice challenge (smallest set of N elements, lower sum limit 5)
31st Aug 2019, 7:58 AM
bell
bell - avatar
0
https://www.sololearn.com/Profile/6305872/?ref=app Thank you! I did not know there were sets in C++ but your lesson prompted me to look for them. In C++ they are even sorted by default! size will tell me if sums are unique but maybe there is a faster way of checking at insertion time to interrupt the moment duplication occurs.
31st Aug 2019, 9:30 AM
bell
bell - avatar