Amenable numbers
Given a number N, the task is to check if N is an Amenable Number or not. If N is an Amenable number then print “Yes” else print “No”.
Amenable numbers are numbers if there exists a multiset of integers whose size, sum and product equal to the number.
For example, 8 is an Amenable Number because there is a multiset of integers {-1, -1, 1, 1, 1, 1, 2, 4} whose size, sum and product is 8.
Examples:
Input: N = 8
Output: Yes
Explanation:
8 is an Amenable Number because there is a multiset of integers {-1, -1, 1, 1, 1, 1, 2, 4} whose size, sum and product is 8.
Input: N = 30
Output: No
Explanation:
30 is not an Amenable Number because there doesn’t exists a multiset of integers whose size, sum and product is 30.
Approach:
The first few Amenable Numbers are 1, 5, 8, 9, 12, 13, 16, 17, 20, 21….. which can be represented as the form 4K or 4K + 1.
Therefore, any number N of the form 4K or 4K + 1 is an Amenable Numbers.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if N // is Amenable number bool isAmenableNum( int N) { // Return true if N is of the form // 4K or 4K + 1 return (N % 4 == 0 || (N - 1) % 4 == 0); } // Driver Code int main() { // Given Number int n = 8; // Function Call if (isAmenableNum(n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program for the above approach class GFG{ // Function to check if N // is Amenable number static boolean isAmenableNum( int N) { // Return true if N is of the form // 4K or 4K + 1 return (N % 4 == 0 || (N - 1 ) % 4 == 0 ); } // Driver code public static void main(String[] args) { int n = 8 ; if (isAmenableNum(n)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by shubham |
Python3
# Python3 program for the above approach import math # Function to check if N # is Amenable number def isAmenableNum(N): # Return true if N is of the # form 4K or 4K + 1 return (N % 4 = = 0 or (N - 1 ) % 4 = = 0 ); # Driver code # Given number N = 8 ; # Function call if (isAmenableNum(N)): print ( "Yes" ); else : print ( "No" ); # This code is contributed by rock_cool |
C#
// C# program for the above approach using System; class GFG{ // Function to check if N // is Amenable number static bool isAmenableNum( int N) { // Return true if N is of the form // 4K or 4K + 1 return (N % 4 == 0 || (N - 1) % 4 == 0); } // Driver code public static void Main(String[] args) { int n = 8; if (isAmenableNum(n)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript program for the above approach // Function to check if N // is Amenable number function isAmenableNum( N) { // Return true if N is of the form // 4K or 4K + 1 return (N % 4 == 0 || (N - 1) % 4 == 0); } // Driver code let n = 8; if (isAmenableNum(n)) { document.write( "Yes" ); } else { document.write( "No" ); } // This code is contributed by Rajput-Ji. </script> |
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)