Minimum value exceeding X whose count of divisors has different parity with count of divisors of X
Given an integer X, the task is to determine the minimum value of Y greater than X, such that count of divisors of X and Y have different parities.
Examples:
Input: X = 5
Output: 9
Explanation: The count of divisors of 5 and 9 are 2 and 3 respectively, which are of different parities.Input: X = 9
Output: 10
Explanation: The counts of divisors of 9 and 10 are 3 and 4, which are of different parities.
Naive Approach: The simplest approach to solve the problem is to iterate each number starting from X + 1 until an element with count of the divisors with parity opposite to that of X is obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count divisors of n int divisorCount( int n) { int x = 0; for ( int i = 1; i <= sqrt (n); i++) { if (n % i == 0) { if (i == n / i) x++; else x += 2; } } return x; } // Function to find the minimum // value exceeding x whose count // of divisors has different parity // with count of divisors of X int minvalue_y( int x) { // Divisor count of x int a = divisorCount(x); int y = x + 1; // Iterate from x + 1 and // check for each element while ((a & 1) == (divisorCount(y) & 1)) y++; return y; } // Driver Code int main() { // Given X int x = 5; // Function call cout << minvalue_y(x) << endl; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count divisors of n static int divisorCount( int n) { int x = 0 ; for ( int i = 1 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) { if (i == n / i) x++; else x += 2 ; } } return x; } // Function to find the minimum // value exceeding x whose count // of divisors has different parity // with count of divisors of X static int minvalue_y( int x) { // Divisor count of x int a = divisorCount(x); int y = x + 1 ; // Iterate from x + 1 and // check for each element while ((a & 1 ) == (divisorCount(y) & 1 )) y++; return y; } // Driver Code public static void main(String[] args) { // Given X int x = 5 ; // Function call System.out.println(minvalue_y(x)); } } // This code is contributed by chitranayal |
C#
// C# program for the above approach using System; class GFG{ // Function to count divisors of n static int divisorCount( int n) { int x = 0; for ( int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { if (i == n / i) x++; else x += 2; } } return x; } // Function to find the minimum // value exceeding x whose count // of divisors has different parity // with count of divisors of X static int minvalue_y( int x) { // Divisor count of x int a = divisorCount(x); int y = x + 1; // Iterate from x + 1 and // check for each element while ((a & 1) == (divisorCount(y) & 1)) y++; return y; } // Driver Code public static void Main() { // Given X int x = 5; // Function call Console.WriteLine(minvalue_y(x)); } } // This code is contributed by susmitakundugoaldanga |
Python3
# Python program for the above approach # Function to count divisors of n def divisorCount(n): x = 0 ; for i in range ( 1 , n): if (n % i = = 0 ): if (i = = n / / i): x + = 1 ; else : x + = 2 ; if (i * i > n): break ; return x; # Function to find the minimum # value exceeding x whose count # of divisors has different parity # with count of divisors of X def minvalue_y(x): # Divisor count of x a = divisorCount(x); y = x + 1 ; # Iterate from x + 1 and # check for each element while ((a & 1 ) = = (divisorCount(y) & 1 )): y + = 1 ; return y; # Driver Code if __name__ = = '__main__' : # Given X x = 5 ; # Function call print (minvalue_y(x)); # This code is contributed by 29AjayKumar |
Javascript
<script> // javascript program of the above approach // Function to count divisors of n function divisorCount(n) { let x = 0; for (let i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { if (i == n / i) x++; else x += 2; } } return x; } // Function to find the minimum // value exceeding x whose count // of divisors has different parity // with count of divisors of X function minvalue_y(x) { // Divisor count of x let a = divisorCount(x); let y = x + 1; // Iterate from x + 1 and // check for each element while ((a & 1) == (divisorCount(y) & 1)) y++; return y; } // Driver Code // Given X let x = 5; // Function call document.write(minvalue_y(x)); // This code is contributed by target_2. </script> |
9
Time Complexity: O((1+√X)2)
Auxiliary Space: O(1)
Efficient Approach: The problem can be solved based on the following observations:
- If X is a perfect square, then X + 1 will be the answer.
- Otherwise, (1 + √X)2 will be the answer.
Follow the steps below to solve the problem:
- Check if X is a perfect square. If found to be true, print X + 1.
- Otherwise, print (1 + floor(√X))2).
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 the minimum // value exceeding x whose count // of divisors has different parity // with count of divisors of X int minvalue_y( int x) { // Check if x is // perfect square int n = sqrt (x); if (n * n == x) return x + 1; return pow (n + 1, 2); } // Driver Code int main() { int x = 5; cout << minvalue_y(x) << endl; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the minimum // value exceeding x whose count // of divisors has different parity // with count of divisors of X static int minvalue_y( int x) { // Check if x is // perfect square int n = ( int )Math.sqrt(x); if (n * n == x) return x + 1 ; return ( int )Math.pow(n + 1 , 2 ); } // Driver Code public static void main(String[] args) { int x = 5 ; System.out.print(minvalue_y(x)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to find the minimum # value exceeding x whose count # of divisors has different parity # with count of divisors of X def minvalue_y(x): # Check if x is # perfect square n = int ( pow (x, 1 / 2 )) if (n * n = = x): return x + 1 return ( pow (n + 1 , 2 )) # Driver Code if __name__ = = '__main__' : x = 5 print (minvalue_y(x)) # This code is contributed by Rajput-Ji |
C#
// C# program for the above approach using System; class GFG{ // Function to find the minimum // value exceeding x whose count // of divisors has different parity // with count of divisors of X static int minvalue_y( int x) { // Check if x is // perfect square int n = ( int )Math.Sqrt(x); if (n * n == x) return x + 1; return ( int )Math.Pow(n + 1, 2); } // Driver Code public static void Main() { int x = 5; Console.WriteLine(minvalue_y(x)); } } // This code is contributed by code_hunt |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the minimum // value exceeding x whose count // of divisors has different parity // with count of divisors of X function minvalue_y(x) { // Check if x is // perfect square let n = Math.floor(Math.sqrt(x)); if (n * n == x) return x + 1; return Math.floor(Math.pow(n + 1, 2)); } // Driver code let x = 5; document.write(minvalue_y(x)); </script> |
9
Time Complexity: O(logx) for input x because using inbuilt sqrt function
Auxiliary Space: O(1)