We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #103: Special subset sums: optimum

Project Euler #103: Special subset sums: optimum

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 103 from projecteuler.net

Let represent the sum of elements in set of size . We shall call it a special sum set if for any two non-empty disjoint subsets, and , the following properties are true:

i. ; that is, sums of subsets cannot be equal.
ii. If contains more elements than then .

If is minimised for a given , we shall call it an optimum special sum set. The first five optimum special sum sets are given below.

It seems that for a given optimum set, , the next optimum set is of the form , where is the "middle" element on the previous row.

By applying this "rule" we would expect the optimum set for to be , with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for is , with .

Let's call the sets obtained by the algorithm above continuously the near-optimal sets. What is the near-optimal set of the size ?

Input Format

The only line containing the number where

Output Format

The only line containing numbers separated by spaces which are the members of the set in ascending order. As the numbers could be huge output them modulo .

Sample Input

6

Sample Output

11 17 20 22 23 24

Author

MarcusAndrews

Difficulty

Easy

Max Score

100

Submitted By

800

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy