Given an integer num and K, we have to count the number of K-beauty substrings possible for the given integer num. There are two conditions that need to be satisfied by the substring to become K-beauty.
- The substring must be of length K.
- The integer form of substring is a divisor of given integer num.
Note: Leading zeros are allowed in the substrings and 0 is not a divisor of any integer value.
Example 1:
Input: num = 360, K = 2
Output: 2
Explanation: Consider the given integer as a string.
"36" is a substring of "360" and 36 is a divisor of 360.
"60" is a substring of "360" and 60 is a divisor of 360.
Count of K-beauty possible = 2
Example 2:
Input: num = 540540, K = 3
Output: 3
Explanation: Consider the given integer as a string.
"540" is a substring of "540540" and 540 is a divisor of 540540.
"405" is a substring of "540540" and 405 is not a divisor of 540540.
"054" is a substring of "540540" and 054 is a divisor of 540540.
"540" is a substring of "540540" and 540 is a divisor of 540540.
Count of K-beauty possible = 3
Approach 1: Fixed-Sized Sliding Window.
This question can be easily solved using the fixed-sized sliding window technique as our window size K is already given in the question.
- Convert the given num integer to a string using the to_string(num) property in C++.
- Initialize the i and j pointers with 0 to calculate the size of our sliding window and one count variable to get the count of K-beauty.
- Run a while loop for our string size and keep on increasing our window size until our window size become equal to K. (j-i+1 == K)
- Extract the string using the substring function and convert that string to an integer n.
- Check whether the converted number n is a divisor of given integer num. If Yes, then increase the count.
- Return the count as an output.
C++ Code for finding the K-beauty of a number:
#include<iostream> #include <string> using namespace std; int KBeautyCount(int num, int K){ //convert the given num to string string str = to_string(num); //initialize i and j for window size int i = 0, j = 0, count = 0; while(j < str.size()){ if(j-i+1 < K){ //increment the j to get window size j++; } else if(j-i+1 == K){ //get the substring and convert it to integer string s = str.substr(i, K); int n = stoi(s); //check if n is divisor of num if(n != 0 && num % n == 0){ count++; } i++; j++; } } return count; } int main(){ int num = 540540; int K = 3; cout<<KBeautyCount(num, K); }
Output:
3- Time Complexity: O(n)
- Space Complexity: O(1)
Approach 2: Using a single for loop and substring property.
In this very easy and brute force approach, we just need to run a for loop and extra the substring of size K and then convert that substring into an integer and check whether the given condition is satisfied by that integer or not. Similarly, check the condition for all possible substrings of size K.
C++ Code for finding the K-beauty of a number:
#include<iostream> #include <string> using namespace std; int KBeautyCount(int num, int K){ //convert the given num to string string str = to_string(num); //Size of String int n = str.size(); int count = 0; for(int i = 0; i < n-K+1; i++){ //extract the substring of size K string s = str.substr(i,K); //convert the string to integer int snum = stoi(s); if(snum != 0 && num % snum == 0){ count++; } } return count; } int main(){ int num = 540540; int K = 3; cout<<KBeautyCount(num, K); }
Output:
3- Time Complexity: O(n)
- Space Complexity: O(1)
👉Support Us by Sharing our post with others if you really found this useful and also share your valuable feedback in the comment section below so we can work on them and provide you best 😊.(alert-success)
No comments:
Post a Comment