Given an array arr[] of N integers and an integer K, the task is to find a subarray of length K with a sum of elements equal to factorial of any number. If no such subarray exists, print “-1”.
Examples:
Input: arr[] = {23, 45, 2, 4, 6, 9, 3, 32}, K = 5
Output: 2 4 6 9 3
Explanation:
Subarray {2, 4, 6, 9, 3} with sum 24 (= 4!) satisfies the required condition.Input: arr[] = {23, 45, 2, 4, 6, 9, 3, 32}, K = 3
Output: -1
Explanation:
No such subarray of length K (= 3) exists.
Naive Approach: The simplest approach to solve the problem is to calculate the sum of all subarrays of length K and check if any of those sums is factorial of any number. If found to be true for any subarray, print that subarray. Otherwise, print “-1”.
Time Complexity: O(N*K)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the Sliding Window technique to calculate the sum of all subarrays of length K and then check if the sum is a factorial or not. Below are the steps:
- Calculate the sum of first K array elements and store the sum in a variable, say sum.
- Then traverse the remaining array and keep updating sum to get the sum of the current subarray of size K by subtracting the first element from the previous subarray and adding the current array element.
- To check whether the sum is a factorial of a number or not, divide the sum by 2, 3, and so on until it cannot be divided further. If the number reduces to 1, the sum is the factorial of a number.
- If the sum in the above step is a factorial of a number, store the starting and ending index of that subarray to print the subarray.
- After completing the above steps, if no such subarray is found, print “-1”. Otherwise, print the subarray whose start and end indices are stored.
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 a number// is factorial of a number or notint isFactorial(int n){ int i = 2; while (n != 1) { // If n is not a factorial if (n % i != 0) { return 0; } n /= i; i++; } return i - 1;}// Function to return the index of// the valid subarraypair<int, int> sumFactorial( vector<int> arr, int K){ int i, sum = 0, ans; // Calculate the sum of // first subarray of length K for (i = 0; i < K; i++) { sum += arr[i]; } // Check if sum is a factorial // of any number or not ans = isFactorial(sum); // If sum of first K length subarray // is factorial of a number if (ans != 0) { return make_pair(ans, 0); } // Find the number formed from the // subarray which is a factorial for (int j = i; j < arr.size(); j++) { // Update sum of current subarray sum += arr[j] - arr[j - K]; // Check if sum is a factorial // of any number or not ans = isFactorial(sum); // If ans is true, then return // index of the current subarray if (ans != 0) { return make_pair(ans, j - K + 1); } } // If the required subarray is // not possible return make_pair(-1, 0);}// Function to print the subarray whose// sum is a factorial of any numbervoid printRes(pair<int, int> answer, vector<int> arr, int K){ // If no such subarray exists if (answer.first == -1) { cout << -1 << endl; } // Otherwise else { int i = 0; int j = answer.second; // Iterate to print subarray while (i < K) { cout << arr[j] << " "; i++; j++; } }}// Driver Codeint main(){ vector<int> arr = { 23, 45, 2, 4, 6, 9, 3, 32 }; // Given sum K int K = 5; // Function Call pair<int, int> answer = sumFactorial(arr, K); // Print the result printRes(answer, arr, K); return 0;} |
Java
// Java program for the above approach import java.util.*;import java.io.*;class GFG{ // Pair classpublic static class Pair{ int x; int y; Pair(int x, int y) { this.x = x; this.y = y; }}// Function to check if a number // is factorial of a number or not static int isFactorial(int n) { int i = 2; while (n != 1) { // If n is not a factorial if (n % i != 0) { return 0; } n /= i; i++; } return i - 1; }// Function to return the index of // the valid subarray static ArrayList<Pair> sumFactorial(int arr[], int K) { ArrayList<Pair> pair = new ArrayList<>(); int i, sum = 0, ans; // Calculate the sum of // first subarray of length K for(i = 0; i < K; i++) { sum += arr[i]; } // Check if sum is a factorial // of any number or not ans = isFactorial(sum); // If sum of first K length subarray // is factorial of a number if (ans != 0) { Pair p = new Pair(ans, 0); pair.add(p); return pair; } // Find the number formed from the // subarray which is a factorial for(int j = i; j < arr.length; j++) { // Update sum of current subarray sum += arr[j] - arr[j - K]; // Check if sum is a factorial // of any number or not ans = isFactorial(sum); // If ans is true, then return // index of the current subarray if (ans != 0) { Pair p = new Pair(ans, j - K + 1); pair.add(p); return pair; } } // If the required subarray is // not possible Pair p = new Pair(-1, 0); pair.add(p); return pair;} // Function to print the subarray whose // sum is a factorial of any number static void printRes(ArrayList<Pair> answer, int arr[], int K) { // If no such subarray exists if (answer.get(0).x == -1) { // cout << -1 << endl; System.out.println("-1"); } // Otherwise else { int i = 0; int j = answer.get(0).y; // Iterate to print subarray while (i < K) { System.out.print(arr[j] + " "); i++; j++; } } } // Driver Code public static void main(String args[]) { // Given array arr[] and brr[] int arr[] = { 23, 45, 2, 4, 6, 9, 3, 32 }; int K = 5; ArrayList<Pair> answer = new ArrayList<>(); // Function call answer = sumFactorial(arr,K); // Print the result printRes(answer, arr, K);} }// This code is contributed by bikram2001jha |
Python3
# Python3 program for the above approach# Function to check if a number# is factorial of a number or notdef isFactorial(n): i = 2 while (n != 1): # If n is not a factorial if (n % i != 0): return 0 n = n // i i += 1 return i - 1# Function to return the index of# the valid subarraydef sumFactorial(arr, K): i, Sum = 0, 0 # Calculate the sum of # first subarray of length K while(i < K): Sum += arr[i] i += 1 # Check if sum is a factorial # of any number or not ans = isFactorial(Sum) # If sum of first K length subarray # is factorial of a number if (ans != 0): return (ans, 0) # Find the number formed from the # subarray which is a factorial for j in range(i, len(arr)): # Update sum of current subarray Sum = Sum + arr[j] - arr[j - K] # Check if sum is a factorial # of any number or not ans = isFactorial(Sum) # If ans is true, then return # index of the current subarray if (ans != 0): return (ans, j - K + 1) # If the required subarray is # not possible return (-1, 0)# Function to print the subarray whose# sum is a factorial of any numberdef printRes(answer, arr, K): # If no such subarray exists if (answer[0] == -1): print(-1) # Otherwise else: i = 0 j = answer[1] # Iterate to print subarray while (i < K): print(arr[j], end = " ") i += 1 j += 1# Driver code arr = [ 23, 45, 2, 4, 6, 9, 3, 32 ]# Given sum KK = 5# Function callanswer = sumFactorial(arr, K)# Print the resultprintRes(answer, arr, K)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for // the above approach using System;using System.Collections.Generic;class GFG{ // Pair classpublic class Pair{ public int x; public int y; public Pair(int x, int y) { this.x = x; this.y = y; }}// Function to check if a number // is factorial of a number or not static int isFactorial(int n) { int i = 2; while (n != 1) { // If n is not // a factorial if (n % i != 0) { return 0; } n /= i; i++; } return i - 1; }// Function to return the index of // the valid subarray static List<Pair> sumFactorial(int []arr, int K) { List<Pair> pair = new List<Pair>(); int i, sum = 0, ans; // Calculate the sum of // first subarray of length K for(i = 0; i < K; i++) { sum += arr[i]; } // Check if sum is a factorial // of any number or not ans = isFactorial(sum); // If sum of first K length subarray // is factorial of a number if (ans != 0) { Pair p = new Pair(ans, 0); pair.Add(p); return pair; } // Find the number formed from the // subarray which is a factorial for(int j = i; j < arr.Length; j++) { // Update sum of current subarray sum += arr[j] - arr[j - K]; // Check if sum is a factorial // of any number or not ans = isFactorial(sum); // If ans is true, then return // index of the current subarray if (ans != 0) { Pair p = new Pair(ans, j - K + 1); pair.Add(p); return pair; } } // If the required subarray is // not possible Pair p1 = new Pair(-1, 0); pair.Add(p1); return pair;} // Function to print the subarray whose // sum is a factorial of any number static void printRes(List<Pair> answer, int []arr, int K) { // If no such subarray exists if (answer[0].x == -1) { // cout << -1 << endl; Console.WriteLine("-1"); } // Otherwise else { int i = 0; int j = answer[0].y; // Iterate to print subarray while (i < K) { Console.Write(arr[j] + " "); i++; j++; } } } // Driver Code public static void Main(String []args) { // Given array []arr and brr[] int []arr = {23, 45, 2, 4, 6, 9, 3, 32}; int K = 5; List<Pair> answer = new List<Pair>(); // Function call answer = sumFactorial(arr, K); // Print the result printRes(answer, arr, K);} }// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for the above approach // Function to check if a number // is factorial of a number or not function isFactorial(n) { let i = 2; while (n != 1) { // If n is not a factorial if (n % i != 0) { return 0; } n = parseInt(n / i, 10); i++; } return i - 1; } // Function to return the index of // the valid subarray function sumFactorial(arr,K) { let i, sum = 0, ans; // Calculate the sum of // first subarray of length K for (i = 0; i < K; i++) { sum += arr[i]; } // Check if sum is a factorial // of any number or not ans = isFactorial(sum); // If sum of first K length subarray // is factorial of a number if (ans != 0) { return [ans, 0]; } // Find the number formed from the // subarray which is a factorial for (let j = i; j < arr.length; j++) { // Update sum of current subarray sum += arr[j] - arr[j - K]; // Check if sum is a factorial // of any number or not ans = isFactorial(sum); // If ans is true, then return // index of the current subarray if (ans != 0) { return [ans, j - K + 1]; } } // If the required subarray is // not possible return [-1, 0]; } // Function to print the subarray whose // sum is a factorial of any number function printRes(answer,arr,K) { // If no such subarray exists if (answer[0] == -1) { document.write(-1); } // Otherwise else { let i = 0; let j = answer[1]; // Iterate to print subarray while (i < K) { document.write(arr[j] + " "); i++; j++; } } } // Driver Code let arr= [ 23, 45, 2, 4, 6, 9, 3, 32 ]; // Given sum K let K = 5; // Function Call let answer= sumFactorial(arr, K); // Print the result printRes(answer, arr, K);</script> |
Output:
2 4 6 9 3
Time Complexity: O(N)
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!
