Check if K distinct positive even integers with given sum exists or not
Given two integers N and K, the task is to find if there exist K distinct positive even integers such that their sum is equal to the given number N.
Examples:
Input: N = 16, K = 3
Output: Yes
Explanation: Three distinct positive even integers with sum 16 are 8, 6 and 2.
Since, three such numbers exist, print “YES”.Input: N = 18 K = 4
Output: No
Explanation: Sum of four distinct positive even integers cannot be equal to 18. Hence, print “NO”.
Approach: The idea to solve this problem is to observe that if N is odd, then it will be impossible to get required N by K even numbers. If N is even, then find the sum of the first K even numbers and if their sum is less than or equal to N, then print “YES”. Otherwise, there does not exist K distinct even integers with sum equal to N.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find if the sum // of K even integers equals N void isPossibleN( int N, int K) { // If N is odd, then its impossible // to obtain N from K even numbers if (N % 2 == 1) { cout << "NO" << endl; return ; } // Sum first k even numbers int sum = K * (K + 1); // If sum is less than equal to N if (sum <= N) { cout << "YES" << endl; } // Otherwise else { cout << "No" << endl; } return ; } // Driver Code int main() { int N = 16; int K = 3; isPossibleN(N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { static void isPossibleN( int N, int K) { // If N is odd, then its impossible // to obtain N from K even numbers if (N % 2 == 1 ) { System.out.println( "NO" ); return ; } // Sum first k even numbers int sum = K * (K + 1 ); // If sum is less than equal to N if (sum <= N) { System.out.println( "YES" ); } // Otherwise else { System.out.println( "No" ); } } // Driver Code public static void main(String args[]) { int N = 16 ; int K = 3 ; isPossibleN(N, K); } } // This code is contributed by jana_sayantan. |
Python3
# Python3 program for the above approach # Function to find if the sum # of K even integers equals N def isPossibleN(N, K) : # If N is odd, then its impossible # to obtain N from K even numbers if (N % 2 = = 1 ) : print ( "NO" ) return # Sum first k even numbers sum = K * (K + 1 ) # If sum is less than equal to N if ( sum < = N) : print ( "YES" ) # Otherwise else : print ( "NO" ) return # Driver Code N = 16 K = 3 isPossibleN(N, K) |
C#
// C# implementation of the // above approach using System; class GFG { static void isPossibleN( int N, int K) { // If N is odd, then its impossible // to obtain N from K even numbers if (N % 2 == 1) { Console.WriteLine( "NO" ); return ; } // Sum first k even numbers int sum = K * (K + 1); // If sum is less than equal to N if (sum <= N) { Console.WriteLine( "YES" ); } // Otherwise else { Console.WriteLine( "No" ); } } // Driver Code public static void Main() { int N = 16; int K = 3; isPossibleN(N, K); } } // This code is contributed by jana_sayantan. |
Javascript
<script> function isPossibleN( N, K) { // If N is odd, then its impossible // to obtain N from K even numbers if (N % 2 == 1) { document.write( "NO" ); return ; } // Sum first k even numbers let sum = K * (K + 1); // If sum is less than equal to N if (sum <= N) { document.write( "YES" ); } // Otherwise else { document.write( "No" ); } } // Driver Code let N = 16; let K = 3; isPossibleN(N, K); //this code is contributed by sravan kumar </script> |
YES
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach 2:
Here’s another approach to solve the problem:
- Take two integers, N and K.
- If K is greater than N/2, return “NO”, since we cannot obtain K even numbers whose sum is equal to N.
- If N is even and K is odd, return “NO”, since the sum of K even numbers will always be even.
- Otherwise, return “YES”.
Here are the codes for the same:
C++
#include <bits/stdc++.h> using namespace std; string isPossibleN( int N, int K) { // Check if K is greater than N/2 if (K > N/2) return "NO" ; // Check if N is even and K is odd if (N % 2 == 0 && K % 2 == 1) return "YES" ; return "NO" ; } int main() { int N = 16; int K = 3; cout << isPossibleN(N, K); return 0; } |
Java
import java.util.*; public class Main { public static String isPossibleN( int N, int K) { // Check if K is greater than N/2 if (K > N / 2 ) return "NO" ; // Check if N is even and K is odd if (N % 2 == 0 && K % 2 == 1 ) return "YES" ; return "NO" ; } public static void main(String[] args) { int N = 16 ; int K = 3 ; System.out.println(isPossibleN(N, K)); } } |
Python3
def is_possible_N(N, K): # Check if K is greater than N/2 if K > N / / 2 : return "NO" # Check if N is even and K is odd if N % 2 = = 0 and K % 2 = = 1 : return "YES" return "NO" if __name__ = = '__main__' : N = 16 K = 3 print (is_possible_N(N, K)) |
C#
using System; class GFG { static string IsPossibleN( int N, int K) { // Check if K is greater than N/2 if (K > N / 2) return "NO" ; // Check if N is even and K is odd if (N % 2 == 0 && K % 2 == 1) return "YES" ; return "NO" ; } static void Main() { int N = 16; int K = 3; Console.WriteLine(IsPossibleN(N, K)); } } |
Javascript
function isPossibleN(N, K) { // Check if K is greater than N/2 if (K > Math.floor(N / 2)) return "NO" ; // Check if N is even and K is odd if (N % 2 === 0 && K % 2 === 1) return "YES" ; return "NO" ; } const N = 16; const K = 3; console.log(isPossibleN(N, K)); |
YES
Time Complexity: O(1)
Auxiliary Space: O(1)