Given an integer N, the task is to partition the squares of first N( always a multiple of 8 ) natural numbers into two sets such that the difference of their subset sums is minimized. Print both the subsets as the required answer.
Examples:
Input: N = 8
Output:
0
1 16 36 49
4 9 25 64
Explanation: Squares of first N natural numbers are {1, 4, 9, 16, 25, 36, 49, 64}
Subsets {1, 16, 36, 49} and {4, 9, 25, 64} have sum 102. Therefore, difference of their sums is 0.Input: N = 16
Output:
0
1 16 36 49 81 144 196 225
4 9 25 64 100 121 169 256
Naive Approach: The idea is to generate all possible pair of subsets splitting squares of first N natural numbers in between them and calculate subsets whose difference of the subset sums. Print the pair of subsets for which the difference of their sum is found to be minimum.
Time Complexity: O(N*2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the mathematical properties of the sum of continuous square numbers. Observe that, it is always possible to divide 8 contiguous square numbers into 2 sets such that their subset-sum difference is 0.
Proof:
8 contiguous square numbers can be divided into 2 subsets having difference of their sum as 0.
4 contiguous square numbers can be represented as k2, (k + 1)2, (k + 2)2 and (k + 3)2.Let’s take 1st and 4th element in subset A. Therefore,
Sum of A = k2 + (k+3)2
= 2k2 + 6k + 9Let’s take 2nd and 3rd element in subset B. Therefore,
Sum of B = (k + 1)2 + (k + 2)2
= 2k2 + 6k + 5
Subset difference = Sum of A – Sum of B = 4Hence, 4 contiguous square numbers can be divided into 2 subsets having difference of their sum as 4.
Now, Lets say, the array of contiguous square is arr[] = {a1, a2, a3, a4, a5, a6, a7, a8}.
From the above property, it can be written that:
a1 + a4 – (a2 + a3) = 4 and
a5 + a8 – (a6 + a7) = 4Subtracting the above equations:
a1 + a4 – (a2 + a3) – (a5 + a8 – (a6 + a7)) = 0
Therefore, (a1 + a4 + a6 + a7) – (a2 + a3 + a5 + a8) = 0
Hence, 8 contiguous square numbers can be divided into 2 subsets having difference as 0.
Follow the steps below to solve the problem:
- Initialize a variable to store minimum subset difference and declare it to 0.
- Initialize variable cnt to store the number of blocks of size 8 and divide N by 8 and store it in the variable cnt.
- Initialize a string partition and store the partition pattern of N elements by concatenating string “ABBABAAB”, cnt number of times where “ABBABAAB” represents the subset that each element in a subarray of size 8 has to go in.
- Initialize 2 vectors A and B to store elements of subset A and subset B.
- Iterate a loop over the range [0, N – 1] and insert (i + 1)2 in vector A if pattern[i] is ‘A’. Otherwise, insert (i + 1)2 in vector B.
- After the above steps, print the minimum subset difference, vector A and vector B.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to partition squares of N// natural number in two subsetvoid minimumSubsetDifference(int N){ // Store the count of blocks of size 8 int blockOfSize8 = N / 8; // Partition of block of 8 element string str = "ABBABAAB"; // Store the minimum subset difference int subsetDifference = 0; // Partition of N elements to minimize // their subset sum difference string partition = ""; while (blockOfSize8--) { partition += str; } // Store elements of subset A and B vector<int> A, B; for (int i = 0; i < N; i++) { // If element is of type A if (partition[i] == 'A') { A.push_back((i + 1) * (i + 1)); } // If the element is of type B else { B.push_back((i + 1) * (i + 1)); } } // Print the minimum subset difference cout << subsetDifference << "\n"; // Print the first subset for (int i = 0; i < A.size(); i++) cout << A[i] << " "; cout << "\n"; // Print the second subset for (int i = 0; i < B.size(); i++) cout << B[i] << " ";}// Driver Codeint main(){ int N = 8; // Function Call minimumSubsetDifference(N); return 0;} |
Java
// Java program for the above approach import java.util.Arrays;class GFG{// Function to partition squares of N// natural number in two subsetstatic void minimumSubsetDifference(int N){ // Store the count of blocks of size 8 int blockOfSize8 = N / 8; // Partition of block of 8 element String str = "ABBABAAB"; // Store the minimum subset difference int subsetDifference = 0; // Partition of N elements to minimize // their subset sum difference String partition = ""; while (blockOfSize8-- > 0) { partition += str; } // Store elements of subset A and B int A[] = new int[N]; int B[] = new int[N]; int x = 0, y = 0; for(int i = 0; i < N; i++) { // If element is of type A if (partition.charAt(i) == 'A') { A[x++] = ((i + 1) * (i + 1)); } // If the element is of type B else { B[y++] = ((i + 1) * (i + 1)); } } // Print the minimum subset difference System.out.println(subsetDifference); // Print the first subset for(int i = 0; i < x; i++) System.out.print(A[i] + " "); System.out.println(); // Print the second subset for(int i = 0; i < y; i++) System.out.print(B[i] + " ");}// Driver Codepublic static void main(String[] args){ int N = 8; // Function Call minimumSubsetDifference(N);}}// This code is contributed by shailjapriya |
Python3
# Python3 program for the above approach# Function to partition squares of N# natural number in two subsetdef minimumSubsetDifference(N): # Store the count of blocks of size 8 blockOfSize8 = N // 8 # Partition of block of 8 element str = "ABBABAAB" # Store the minimum subset difference subsetDifference = 0 # Partition of N elements to minimize # their subset sum difference partition = "" while blockOfSize8 != 0: partition = partition + str blockOfSize8 = blockOfSize8 - 1 # Store elements of subset A and B A = [] B = [] for i in range(N): # If element is of type A if partition[i] == 'A': A.append((i + 1) * (i + 1)) # If the element is of type B else: B.append((i + 1) * (i + 1)) # Print the minimum subset difference print(subsetDifference) # Print the first subset for i in A: print(i, end = " ") print() # Print the second subset for i in B: print(i, end = " ")# Driver CodeN = 8# Function callminimumSubsetDifference(N)# This code is contributed by shailjapriya |
C#
// C# program for the above approach using System;class GFG{ // Function to partition squares of N // natural number in two subset static void minimumSubsetDifference(int N) { // Store the count of blocks of size 8 int blockOfSize8 = N / 8; // Partition of block of 8 element string str = "ABBABAAB"; // Store the minimum subset difference int subsetDifference = 0; // Partition of N elements to minimize // their subset sum difference string partition = ""; while (blockOfSize8-- > 0) { partition += str; } // Store elements of subset A and B int []A = new int[N]; int []B = new int[N]; int x = 0, y = 0; for(int i = 0; i < N; i++) { // If element is of type A if (partition[i] == 'A') { A[x++] = ((i + 1) * (i + 1)); } // If the element is of type B else { B[y++] = ((i + 1) * (i + 1)); } } // Print the minimum subset difference Console.WriteLine(subsetDifference); // Print the first subset for(int i = 0; i < x; i++) Console.Write(A[i] + " "); Console.WriteLine(); // Print the second subset for(int i = 0; i < y; i++) Console.Write(B[i] + " "); } // Driver Code public static void Main(string[] args) { int N = 8; // Function Call minimumSubsetDifference(N); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// javascript program to implement// the above approach// Function to partition squares of N// natural number in two subsetfunction minimumSubsetDifference(N){ // Store the count of blocks of size 8 let blockOfSize8 = N / 8; // Partition of block of 8 element let str = "ABBABAAB"; // Store the minimum subset difference let subsetDifference = 0; // Partition of N elements to minimize // their subset sum difference let partition = ""; while (blockOfSize8-- > 0) { partition += str; } // Store elements of subset A and B let A = []; let B = []; let x = 0, y = 0; for(let i = 0; i < N; i++) { // If element is of type A if (partition[i] == 'A') { A[x++] = ((i + 1) * (i + 1)); } // If the element is of type B else { B[y++] = ((i + 1) * (i + 1)); } } // Print the minimum subset difference document.write(subsetDifference + "<br/>"); // Print the first subset for(let i = 0; i < x; i++) document.write(A[i] + " "); document.write("<br/>"); // Print the second subset for(let i = 0; i < y; i++) document.write(B[i] + " ");}// Driver code let N = 8; // Function Call minimumSubsetDifference(N); // This code is contributed by splevel62.</script> |
0 1 16 36 49 4 9 25 64
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
