Given an integer N and a value K, the task is to find the number of factors of length K that are present in the number itself.
Examples:
Input: N = 120, K = 2
Output: 2
Explanation: 12 (120), 20 (120). Both are factors of 120.Input: N = 21, K = 2
Output: 1
Approach: The problem can be solved greedily using the following idea:
Find all the K-length numbers that can be generated from the number and check how many of them are factors of N.
Follow the steps mentioned below to implement the idea:
- Iterate the number.
- Initialize the start index with 0.
- Slice the number for K size from the start index.
- Then check if the sliced part of the number is a factor of the given number.
- If it is a factor, increment the counter.
- Else, do nothing.
- Increment the start index to the next index.
- Continue the above process until the start index is N-K.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the number of factorsint countFactorsinNum(int num, int k){ string str = to_string(num); int N = str.size(); int ctr = 0; int i = 0; while (i <= N - k) { // substr(from where, nos of chars) string s2 = str.substr(i, k); int val = stoi(s2); // val!=0 to avoid div by 0 error if (val != 0 && num % val == 0) { ctr++; } i = i + 1; } return ctr;}// Driver codeint main(){ int N = 120, K = 2; // Function call cout << countFactorsinNum(N, K) << "\n"; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find the number of factors static int countFactorsinNum(int num, int k) { String str = Integer.toString(num); int N = str.length(); int ctr = 0; int i = 0; while (i <= N - k) { // substr(from where, nos of chars) String s2 = str.substring(i, i + k); int val = Integer.parseInt(s2); // val!=0 to avoid div by 0 error if (val != 0 && num % val == 0) { ctr++; } i = i + 1; } return ctr; } // Driver code public static void main(String[] args) { int N = 120, K = 2; // Function call System.out.println(countFactorsinNum(N, K)); }}// This code is contributed by lokesh |
Python3
#Python code for the above approach#Function to find the number of factorsdef countFactorsinNum(num, k): # Convert num to a string str_num = str(num) N = len(str_num) ctr = 0 # Iterate k times starting from the first digit of str_num for i in range(k): # Extract a substring of length k from str_num starting at position i s2 = str_num[i:i+k] # Convert s2 to an integer val = int(s2) # Check if val is a factor of num if val != 0 and num % val == 0: ctr += 1 return ctr# Driver codeN = 120K = 2# Function callprint(countFactorsinNum(N, K))#This code is contributed by Potta Lokesh |
Javascript
// Javascript code to implement the approach// Function to find the number of factorsfunction countFactorsinNum(num, k){ let str = num.toString(); let N = str.length; let ctr = 0; let i = 0; while (i <= N - k) { // substr(from where, nos of chars) let s2 = str.substring(i, k); let val = parseInt(s2); // val!=0 to avoid div by 0 error if (val != 0 && num % val == 0) { ctr++; } i = i + 1; } return ctr;}// Driver code let N = 120, K = 2; // Function call console.log(countFactorsinNum(N, K));// This code is contributed by poojaagarwal2. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class Gfg { static int countFactorsinNum(int num, int k) { string str = num.ToString(); int N = str.Length; int ctr = 0; int i = 0; while (i <= N - k) { // substr(from where, nos of chars) string s2 = str.Substring(i, k); int val = int.Parse(s2); // val!=0 to avoid div by 0 error if (val != 0 && num % val == 0) { ctr++; } i = i + 1; } return ctr; } // Driver code public static void Main(string[] args) { int N = 120, K = 2; // Function call Console.WriteLine(countFactorsinNum(N, K)+"\n"); }} |
Output
2
Time Complexity: O(d) where d is the number of digits
Auxiliary Space: O(1)
Related Articles:
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!
