Checking the validity of a two-integer equation
Given two integers n and k, and an equation 2x + ky = n (1 ≤ k ≤ n). The task is to check whether the equation is valid equation if x and y are whole numbers.
Examples:
Input: n = 8, k = 7
Output: YES
Explanation: The equation is 2x + 7y = 8. The value of y = 0, and x = 4, is a valid answer, and hence the equation is a valid equation.Input: n = 5, k = 2
Output: NO
Explanation: The equation is 2x + 2y = 5. On trying all values of x and y, we can say that, no value of x and y, satisfies the above equation.
Naive Approach: The basic way to solve the problem is as follows:
Rewrite the given equation as, x = (n – ky)/2, we have been given the values of n and k, hence, only y is the variable left on the RHS side. Initialize a variable as n, and decrement the value k from n, each time, and check whether that number is divisible by 2. If at any point the number is divisible by 2, then we have got a valid answer, else no valid answer.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // function finds whether 2x + ky = n, // is a valid equation. void validEquation( int n, int k) { // Decrement the value of n by // k each time. while (n >= 0) { // If divisible by 2, then // valid equation found. if (n % 2 == 0) { break ; } n = n - k; } if (n >= 0) { cout << "YES" << endl; } else { cout << "NO" << endl; } } // Driver code int main() { int n = 8, k = 7; // Function Call validEquation(n, k); return 0; } |
Java
import java.util.*; public class Main { // function finds whether 2x + ky = n, is a valid equation. public static void validEquation( int n, int k) { // Decrement the value of n by k each time. while (n >= 0 ) { // if divisible by 2, then valid equation found. if (n % 2 == 0 ) { break ; } n = n - k; } if (n >= 0 ) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } // Driver code public static void main(String[] args) { int n = 8 , k = 7 ; validEquation(n, k); n = 5 ; k = 2 ; validEquation(n, k); } } // The code is contributed by Nidhi goel. |
Python3
# Python3 code for the above approach: # function finds whether 2x + ky = n, is a valid equation. def validEquation(n, k): # Decrement the value of n by k each time. while n > = 0 : # if divisible by 2, then valid equation found. if n % 2 = = 0 : break n - = k if n > = 0 : print ( "YES" ) else : print ( "NO" ) # Driver code n = 8 k = 7 # Function Call validEquation(n, k) |
C#
using System; class GFG { // function finds whether 2x + ky = n, is a valid // equation. public static void validEquation( int n, int k) { // Decrement the value of n by k each time. while (n >= 0) { // if divisible by 2, then valid equation found. if (n % 2 == 0) { break ; } n = n - k; } if (n >= 0) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } // Driver code public static void Main( string [] args) { int n = 8, k = 7; validEquation(n, k); n = 5; k = 2; validEquation(n, k); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// function finds whether 2x + ky = n, // is a valid equation. function validEquation(n, k) { // Decrement the value of n by // k each time. while (n >= 0) { // If divisible by 2, then // valid equation found. if (n % 2 === 0) { break ; } n = n - k; } if (n >= 0) { console.log( "YES" ); } else { console.log( "NO" ); } } // Driver code const n = 8; const k = 7; validEquation(n, k); |
YES
Time Complexity: O(n)
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
This problem can be solved by some basic maths and even-odd observations. As discussed earlier, the equation can be written as x = (n-ky)/2, hence (n-ky) needs to be an even number, for a valid answer in x. It also means that when this equation is invalid if (n-ky) is an odd number. We know, that for the subtraction of two numbers to be odd, one term should be an even number and another term should be an odd number.
Illustration:
- Now, let us consider a case when n is odd, and k is even, for e.g. n = 5, and k = 2, the equation is x = (5-2y)/2, there is no value for y, for which we could have a valid equation.
- Now, we might be thinking of another case, when n is even, and k is odd, for e.g. n = 6, and k = 3, the equation is x = (6-3y)/2, but the equation gives a valid answer, if y = 0, x = 3, hence it’s a valid equation.
- After the above observations, we can say that, we will only get an invalid equation if n is odd and k is even, else the equation is always valid.
Below are the steps for the above approach:
- Check if n is odd and k is even, then it is an invalid equation and prints NO, else prints YES.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function finds whether 2x + ky = n, // is a valid equation. void validEquation( int n, int k) { // If n is odd and k is even, // then it's an invalid equation if (n % 2 != 0 && k % 2 == 0) { cout << "NO" << endl; } else { cout << "YES" << endl; } } // Driver code int main() { int n = 8, k = 7; // Function Call validEquation(n, k); return 0; } |
Java
// java code for the above approach: import java.util.*; public class Main { // function finds whether 2x + ky = n, is a valid equation. static void validEquation( int n, int k) { // if n is odd and k is even, then it's an invalid equation if (n % 2 != 0 && k % 2 == 0 ) { System.out.println( "NO" ); } else { System.out.println( "YES" ); } } // Driver code public static void main(String[] args) { int n = 8 , k = 7 ; // Function Call validEquation(n, k); n = 5 ; k = 2 ; validEquation(n, k); } } // The code is contributed by Nidhi goel. |
Python3
def validEquation(n, k): # If n is odd and k is even, # then it's an invalid equation if n % 2 ! = 0 and k % 2 = = 0 : print ( "NO" ) else : print ( "YES" ) # Driver code if __name__ = = "__main__" : n = 8 k = 7 # Function Call validEquation(n, k) |
C#
using System; public class Program { // Driver code public static void Main( string [] args) { int n = 8; int k = 7; ValidEquation(n, k); } // Function finds whether 2x + ky = n, // is a valid equation. public static void ValidEquation( int n, int k) { // If n is odd and k is even, // then it's an invalid equation if (n % 2 != 0 && k % 2 == 0) { Console.WriteLine( "NO" ); } else { Console.WriteLine( "YES" ); } } } |
Javascript
// Function to find whether 2x + ky = n is a valid equation function validEquation(n, k) { // If n is odd and k is even, then it's an invalid equation if (n % 2 !== 0 && k % 2 === 0) { console.log( "NO" ); } else { console.log( "YES" ); } } // Driver code let n = 8, k = 7; // Function call validEquation(n, k); n = 5; k = 2; validEquation(n, k); |
YES
Time Complexity: O(1)
Auxiliary Space: O(1)
Approach 3:
- The approach to check whether 2x + ky = n is a valid equation or not is to solve the equation for x and check if the obtained value of x is an integer or not.
- The equation can be rearranged as: x = (n – ky) / 2.
- If (n – ky) is even, then x will be an integer, otherwise not.
- Hence, the validity of the equation depends on the parity of (n – ky).
Here’s the codes for this approach:
C++
#include <bits/stdc++.h> using namespace std; // Function finds whether 2x + ky = n, // is a valid equation. void validEquation( int n, int k) { int x,y; x = (n - k*y)/2; if ((n-k*y)%2==0) cout<< "YES" <<endl; else cout<< "NO" <<endl; } // Driver code int main() { int n = 8, k =7; // Function Call validEquation(n, k); return 0; } |
Java
import java.util.*; public class ValidEquation { // Function finds whether 2x + ky = n, // is a valid equation. public static void validEquation( int n, int k) { int x, y = 0 ; x = (n - k * y) / 2 ; if ((n - k * y) % 2 == 0 ) System.out.println( "YES" ); else System.out.println( "NO" ); } // Driver code public static void main(String[] args) { int n = 8 , k = 7 ; // Function Call validEquation(n, k); } } // This code is contributed by codearcade |
Python
# Function finds whether 2x + ky = n, # is a valid equation. def valid_equation(n, k): y = 0 x = (n - k * y) / / 2 if (n - k * y) % 2 = = 0 : print ( "YES" ) else : print ( "NO" ) # Driver code if __name__ = = "__main__" : n = 8 k = 7 # Function Call valid_equation(n, k) |
C#
using System; class Program { // Function to determine whether the equation 2x + ky = n is valid static void ValidEquation( int n, int k) { int y; // Calculate the value of y based on whether n is even or odd y = (n % 2 == 0) ? 0 : 1; // Check if the equation is valid (remainder is 0) if ((n - k * y) % 2 == 0) { Console.WriteLine( "YES" ); // If valid, print "YES" } else { Console.WriteLine( "NO" ); // If not valid, print "NO" } } // Driver code static void Main() { int n = 8, k = 7; // Function Call ValidEquation(n, k); } } |
Javascript
function validEquation(n, k) { let y = 0; let x = (n - k * y) / 2; if ((n - k * y) % 2 === 0) { console.log( "YES" ); } else { console.log( "NO" ); } } // Driver code let n = 8; let k = 7; // Function Call validEquation(n, k); |
YES
Time Complexity: O(1)
Auxiliary Space: O(1)