Closest sum partition (into two subsets) of numbers from 1 to n
Given an integer sequence 1, 2, 3, 4, ā¦, n. The task is to divide it into two sets A and B in such a way that each element belongs to exactly one set and |sum(A) ā sum(B)| is the minimum possible. Print the value of |sum(A) ā sum(B)|.
Examples:
Input: 3 Output: 0 A = {1, 2} and B = {3} ans |sum(A) - sum(B)| = |3 - 3| = 0. Input: 6 Output: 0 A = {1, 3, 4} and B = {2, 5} ans |sum(A) - sum(B)| = |3 - 3| = 0. Input: 5 Output: 1
Approach:
Take mod = n % 4,
- If mod = 0 or mod = 3 then print 0.
- If mod = 1 or mod = 2 then print 1.
This is because the groups will be chosen as A = {N, N ā 3, N ā 4, N ā 7, N ā 8, ā¦..}, B = {N ā 1, N ā 2, N ā 5, N ā 6, ā¦..}
Starting from N to 1, place 1st element in group A then alternate every 2 elements in B, A, B, A, ā¦..
- When n % 4 = 0: N = 8, A = {1, 4, 5, 8} and B = {2, 3, 6, 7}
- When n % 4 = 1: N = 9, A = {1, 4, 5, 8, 9} and B = {2, 3, 6, 7}
- When n % 4 = 2: N = 10, A = {1, 4, 5, 8, 9} and B = {2, 3, 6, 7, 10}
- When n % 4 = 3: N = 11, A = {1, 4, 5, 8, 9} and B = {2, 3, 6, 7, 10, 11}
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum required // absolute difference int minAbsDiff( int n) { int mod = n % 4; if (mod == 0 || mod == 3) return 0; return 1; } // Driver code int main() { int n = 5; cout << minAbsDiff(n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the minimum required // absolute difference static int minAbsDiff( int n) { int mod = n % 4 ; if (mod == 0 || mod == 3 ) { return 0 ; } return 1 ; } // Driver code public static void main(String[] args) { int n = 5 ; System.out.println(minAbsDiff(n)); } } // This code is contributed by Rajput-JI |
Python 3
# Python3 implementation of the approach # Function to return the minimum required # absolute difference def minAbsDiff(n) : mod = n % 4 ; if (mod = = 0 or mod = = 3 ) : return 0 ; return 1 ; # Driver code if __name__ = = "__main__" : n = 5 ; print (minAbsDiff(n)) # This code is contributed by Ryuga |
C#
// C# implementation of the // above approach using System; class GFG { // Function to return the minimum // required absolute difference static int minAbsDiff( int n) { int mod = n % 4; if (mod == 0 || mod == 3) { return 0; } return 1; } // Driver code static public void Main () { int n = 5; Console.WriteLine(minAbsDiff(n)); } } // This code is contributed by akt_mit |
PHP
<?php // PHP implementation of the approach // Function to return the minimum // required absolute difference function minAbsDiff( $n ) { $mod = $n % 4; if ( $mod == 0 || $mod == 3) return 0; return 1; } // Driver code $n = 5; echo minAbsDiff( $n ); // This code is contributed by Tushil. ?> |
Javascript
<script> // Javascript implementation of the above approach // Function to return the minimum // required absolute difference function minAbsDiff(n) { let mod = n % 4; if (mod == 0 || mod == 3) { return 0; } return 1; } let n = 5; document.write(minAbsDiff(n)); </script> |
1
Time Complexity: O(1) // since no loop is used so the algorithm takes constant time to execute completely.
Auxiliary Space: O(1) // since no extra array is used the algorithm takes up constant space to run completely.