Given an integer N, below operations can be performed any number of times on N:
- Multiply N by any positive integer X i.e. N = N * X.
- Replace N with square root of N (N must be an integer) i.e. N = sqrt(N).
The task is to find the minimum integer to which N can be reduced with the above operations.
Examples:
Input: N = 20
Output: 10
We can multiply 20 by 5, then take sqrt(20*5) = 10, this is the minimum number that 20 can be reduced to with the given operations.Input: N = 36
Output: 6
Take sqrt(36). Number 6 can’t be reduced further.
Approach:
- First factorize the number N.
- Say, 12 has factors 2, 2 and 5. Only the factors that are repeating can be reduced with sqrt(n) i.e. sqrt(2*2) = 2.
- The numbers appearing only once in the factors cannot be further reduced.
- So, the final answer will be the product of all the distinct prime factors of number N
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> #define ll long long int using namespace std; // function to return the product of // distinct prime factors of a number ll minimum(ll n) { ll product = 1; // find distinct prime for ( int i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) n = n / i; product = product * i; } } if (n >= 2) product = product * n; return product; } // Driver code int main() { ll n = 20; cout << minimum(n) << endl; return 0; } |
Java
// Java implementation of the above approach import java.util.*; class solution { // function to return the product of // distinct prime factors of a number static int minimum( int n) { int product = 1 ; // find distinct prime for ( int i = 2 ; i * i <= n; i++) { if (n % i == 0 ) { while (n % i == 0 ) n = n / i; product = product * i; } } if (n >= 2 ) product = product * n; return product; } // Driver code public static void main(String arr[]) { int n = 20 ; System.out.println(minimum(n)); } } //This code is contributed by //Surendra_Gangwar |
Python3
# Python3 implementation of above approach # function to return the product # of distinct prime factors of a # numberdef minSteps(str): def minimum(n): product = 1 # find distinct prime i = 2 while i * i < = n: if n % i = = 0 : while n % i = = 0 : n = n / i product = product * i i = i + 1 if n > = 2 : product = product * n return product # Driver code # Get the binary string n = 20 print (minimum(n)) # This code is contributed # by Shashank_Sharma |
C#
// C# implementation of the above approach class GFG { // function to return the product of // distinct prime factors of a number static int minimum( int n) { int product = 1; // find distinct prime for ( int i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) n = n / i; product = product * i; } } if (n >= 2) product = product * n; return product; } // Driver code static void Main() { int n = 20; System.Console.WriteLine(minimum(n)); } } // This code is contributed by mits |
PHP
<?php // PHP implementation of the // above approach // function to return the product of // distinct prime factors of a number function minimum( $n ) { $product = 1; // find distinct prime for ( $i = 2; $i * $i <= $n ; $i ++) { if ( $n % $i == 0) { while ( $n % $i == 0) $n = $n / $i ; $product = $product * $i ; } } if ( $n >= 2) $product = $product * $n ; return $product ; } // Driver code $n = 20; echo minimum( $n ), "\n" ; // This code is contributed by ANKITRAI1 ?> |
Javascript
<script> // JavaScript implementation of the above approach // function to return the product of // distinct prime factors of a number function minimum( n) { let product = 1; // find distinct prime for (let i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) n = n / i; product = product * i; } } if (n >= 2) product = product * n; return product; } // Driver code let n = 20; document.write(minimum(n)); // This code is contributed by sravan kumar </script> |
10
Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!