Given an integer N, the task is to check whether the elements from the range [1, N] can be divided into three non-empty equal sum subsets. If possible then print Yes else print No.
Examples:
Input: N = 5
Output: Yes
The possible subsets are {1, 4}, {2, 3} and {5}.
(1 + 4) = (2 + 3) = (5)Input: N = 3
Output: No
Approach: There are two cases:
- If N ? 3: In this case, it is not possible to divide the elements in the subsets that satisfy the given condition. So, print No.
- If N > 3: In this case, it is only possible when the sum of all the elements of the range [1, N] is divisible by 3 which can be easily calculated as sum = (N * (N + 1)) / 2. Now, if sum % 3 = 0 then print Yes else print No.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function that returns true // if the subsets are possible bool possible( int n) { // If n <= 3 then it is not possible // to divide the elements in three subsets // satisfying the given conditions if (n > 3) { // Sum of all the elements // in the range [1, n] int sum = (n * (n + 1)) / 2; // If the sum is divisible by 3 // then it is possible if (sum % 3 == 0) { return true ; } } return false ; } // Driver code int main() { int n = 5; if (possible(n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach import java.math.*; class GFG { // Function that returns true // if the subsets are possible public static boolean possible( int n) { // If n <= 3 then it is not possible // to divide the elements in three subsets // satisfying the given conditions if (n > 3 ) { // Sum of all the elements // in the range [1, n] int sum = (n * (n + 1 )) / 2 ; // If the sum is divisible by 3 // then it is possible if (sum % 3 == 0 ) { return true ; } } return false ; } // Driver code public static void main(String[] args) { int n = 5 ; if (possible(n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Naman_Garg |
Python3
# Python3 implementation of the approach # Function that returns true # if the subsets are possible def possible(n) : # If n <= 3 then it is not possible # to divide the elements in three subsets # satisfying the given conditions if (n > 3 ) : # Sum of all the elements # in the range [1, n] sum = (n * (n + 1 )) / / 2 ; # If the sum is divisible by 3 # then it is possible if ( sum % 3 = = 0 ) : return True ; return False ; # Driver code if __name__ = = "__main__" : n = 5 ; if (possible(n)) : print ( "Yes" ); else : print ( "No" ); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function that returns true // if the subsets are possible public static bool possible( int n) { // If n <= 3 then it is not possible // to divide the elements in three subsets // satisfying the given conditions if (n > 3) { // Sum of all the elements // in the range [1, n] int sum = (n * (n + 1)) / 2; // If the sum is divisible by 3 // then it is possible if (sum % 3 == 0) { return true ; } } return false ; } // Driver code static public void Main () { int n = 5; if (possible(n)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by ajit |
Javascript
<script> // Javascript implementation of the approach // Function that returns true // if the subsets are possible function possible(n) { // If n <= 3 then it is not possible // to divide the elements in three subsets // satisfying the given conditions if (n > 3) { // Sum of all the elements // in the range [1, n] let sum = parseInt((n * (n + 1)) / 2); // If the sum is divisible by 3 // then it is possible if (sum % 3 == 0) { return true ; } } return false ; } // Driver code let n = 5; if (possible(n)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by rishavmahato348 </script> |
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!