Given two positive integers N and K, the task is to check if the given integer N can be expressed as the product of K consecutive integers or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: N = 210, K = 3
Output: Yes
Explanation: 210 can be expressed as 5 * 6 * 7.Input: N = 780, K =4
Output: No
Approach: The given problem can be solved by using Sliding Window Technique. Follow the steps below to solve the problem:
- Initialize two integers, say Kthroot and product, to store the Kth root of the integer N and the product of K consecutive integers respectively.
- Store the product of integers over the range [1, K] in the variable product.
- Otherwise, iterate over the range [2, Kthroot] and perform the following steps:
- If the value of the product is equal to N, then print “Yes” and break out of the loop.
- Update the value of product as (product*(i + K – 1)) / (i – 1).
- After completing the above steps, if none of the above cases satisfy, then print “No” as N cannot be expressed as the product of K consecutive integers.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if N can be expressed// as the product of K consecutive integersstring checkPro(int n, int k){ double exp = 1.0 / k; // Stores the K-th root of N int KthRoot = (int)pow(n, exp); // Stores the product of K // consecutive integers int product = 1; // Traverse over the range [1, K] for(int i = 1; i < k + 1; i++) { // Update the product product = product * i; } // If product is N, then return "Yes" if (product == n) return "Yes"; else { // Otherwise, traverse over // the range [2, Kthroot] for(int j = 2; j < KthRoot + 1; j++) { // Update the value of product product = product * (j + k - 1); product = product / (j - 1); // If product is equal to N if (product == n) return "Yes"; } } // Otherwise, return "No" return "No";}// Driver codeint main(){ int N = 210; int K = 3; cout << checkPro(N, K); return 0;}// This code is contributed by avijitmondal1998 |
Java
// Java program for the above approachpublic class GFG { // Function to check if N can be expressed // as the product of K consecutive integers static String checkPro(int n, int k){ double exp = 1.0 / k ; // Stores the K-th root of N int KthRoot = (int)Math.pow(n, exp); // Stores the product of K // consecutive integers int product = 1 ; // Traverse over the range [1, K] for (int i = 1; i < k + 1; i++){ // Update the product product = product * i; } // If product is N, then return "Yes" if(product == n) return "Yes"; else { // Otherwise, traverse over // the range [2, Kthroot] for (int j = 2; j < KthRoot + 1; j++) { // Update the value of product product = product * (j + k - 1) ; product = product / (j - 1) ; // If product is equal to N if(product == n) return "Yes" ; } } // Otherwise, return "No" return "No" ; } // Driver Code public static void main (String[] args) { int N = 210; int K = 3; System.out.println(checkPro(N, K)); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to check if N can be expressed# as the product of K consecutive integersdef checkPro(n, k): # Stores the K-th root of N KthRoot = int(n**(1 / k)) # Stores the product of K # consecutive integers product = 1 # Traverse over the range [1, K] for i in range(1, k + 1): # Update the product product = product * i print(product) # If product is N, then return "Yes" if(product == N): return ("Yes") # Otherwise, traverse over # the range [2, Kthroot] for i in range(2, KthRoot + 1): # Update the value of product product = product*(i + k-1) product = product/(i - 1) print(product) # If product is equal to N if(product == N): return ("Yes") # Otherwise, return "No" return ("No")# Driver CodeN = 210K = 3# Function Callprint(checkPro(N, K)) |
C#
// C# program for the above approachusing System;class GFG{// Function to check if N can be expressed// as the product of K consecutive integersstatic string checkPro(int n, int k){ double exp = 1.0 / k ; // Stores the K-th root of N int KthRoot = (int)Math.Pow(n, exp); // Stores the product of K // consecutive integers int product = 1 ; // Traverse over the range [1, K] for(int i = 1; i < k + 1; i++) { // Update the product product = product * i; } // If product is N, then return "Yes" if (product == n) return "Yes"; else { // Otherwise, traverse over // the range [2, Kthroot] for(int j = 2; j < KthRoot + 1; j++) { // Update the value of product product = product * (j + k - 1); product = product / (j - 1); // If product is equal to N if (product == n) return "Yes"; } } // Otherwise, return "No" return "No";}// Driver Codestatic public void Main(){ int N = 210; int K = 3; Console.WriteLine(checkPro(N, K));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program for the above approach // Function to check if N can be expressed // as the product of K consecutive integers function checkPro(n , k) { var exp = 1.0 / k; // Stores the K-th root of N var KthRoot = parseInt( Math.pow(n, exp)); // Stores the product of K // consecutive integers var product = 1; // Traverse over the range [1, K] for (i = 1; i < k + 1; i++) { // Update the product product = product * i; } // If product is N, then return "Yes" if (product == n) return "Yes"; else { // Otherwise, traverse over // the range [2, Kthroot] for (j = 2; j < KthRoot + 1; j++) { // Update the value of product product = product * (j + k - 1); product = product / (j - 1); // If product is equal to N if (product == n) return "Yes"; } } // Otherwise, return "No" return "No"; } // Driver Code var N = 210; var K = 3; document.write(checkPro(N, K));// This code contributed by Rajput-Ji</script> |
Output:
Yes
Time Complexity: O(K + N(1/K))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
