Two sets program in C++

Today, we will see a basic problem in C++ and try to find an efficient algorithm for it. The problem goes like this. We are given an integer n and we have to divide the numbers 1,2,…,n into two sets such that both the sets have an equal sum. Of course, it is not necessary that both sets have an equal number of elements. Let us understand the problem more deeply and then try to come up with an algorithm and implement it in C++.

Mathematically diving the two sets

First of all, not all given n can give rise to 2 sets as all the elements here are integers. We will see why this is when we see some examples.

Let us say an integer ‘ n ‘ is given as the input, and let ‘ s ‘ be the sum of all the integers 1,2,….,n.

According to the problem the two sets will need to have an equal sum. But since the elements are taken from 1,2,…,n exhaustively, the sum of both the sets will be equal to s again. In other words, if the two sets are possible, each of them will have a sum of s/2 each. So from here, we can deduce that if s is an odd number, then s/2 will not be an integer and hence the division will not be possible using integers. Note that for a given n, there can exist multiple ways of diving the elements into 2 groups and here we just need to find one such arrangement. Let us see a few examples.

Two Sets Examples

Say,n=7

Here, 1,2,3,4,5,6,7 which have to be segregated into two groups with the same sum. Let us first evaluate what that sum should be.

The sum of the first 7 numbers can be calculated as 7*8/2 = 28

Since 28 is even it can be split into two equal numbers, which is 14.

So the split is possible and each group should have a sum of 14. We have to find one set of numbers from the given integers which add up to 14 and the rest will obviously add up to 14.

One such pair of sets can be

6, 5, 3 and 1, 2, 4, 7 . We can see that each group adds up to 14.

However this is not the only possible pair.  7,6,1 and 2,3,4,5 also counts as a solution.

Let us take n=6 now,

here s= 6*7/2=21

Now we cannot split 21 into two equal integers so the split is not possible.

Algorithm

To write an efficient algorithm for this, we can start with the first step as we discussed in the last section.

So first we take input n and calculate sum using the formula.

Then, we check if that is odd, if so, we say it is not possible and terminate the code.

Else, we continue with sum as half its value. We need to find the numbers which add up to this sum now.

For this one method would be to start at n and as long as the number is greater than the sum we keep adding to the first group and keep reducing sum by that number. At a point where sum becomes less than the integer we take that sum and add it to group one. The remaining elements as we discussed will go to group 2. Let us see the C++ code to understand this in a better way.

C++ Code: two sets program

I have used a vector for both the groups to which we can add the elements as we pick them. As we discussed the first part of the code deals with finding the sum of the n numbers and checking if it is even or not. The code will return NO if it is odd. Else, we give YES and continue. We start a loop with n as starting point and keep decrementing by one. We segregate the numbers as we check the sum and change it. Finally, we display both the groups in two seperate lines.

Take a look at the C++ code below:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
  long n,i,n1=0,n2=0;
  long sum;
  vector<int> g1,g2;
  cin>>n;
  sum=n*(n+1)/2;
  if(sum%2==1)
  {
    cout<<"NO";                  // The sum of given n integers is odd
    return 0;
  }
  cout<<"YES\n";
  sum=sum/2;                     // The sum required for each group
  for(i=n;i>0;i--)
   if(i<=sum)
    {
      sum=sum-i;
      g1.push_back(i);           // Adding to first group 
    }
    else 
    {
      if(i!=sum)
      g2.push_back(i);           // Adding to the second group
    }
  if(sum!=0)
   g1.push_back(sum);            // The remaining integer is added to the first group 
  n1=g1.size();                  // Length of the first group
  n2=g2.size();                  // Length of the second group
  for(i=0;i<n1;i++)
    cout<<g1[i]<<" "; 
  cout<<"\n";
  for(i=0;i<n2;i++)
    cout<<g2[i]<<" "; 
  return 0;
}

Example output:

15
YES
15 14 13 12 6
11 10 9 8 7 5 4 3 2 1

This problem is a simpler version for a popular problem called as the knapsack problem, which is also used in cryptography.