Check if a numeric string can be split into substrings having difference between consecutive numbers equal to K
Given a numeric string S consisting of N digits and a positive integer K, the task is to check if the given string can be split into more than one substrings with difference between consecutive substrings equal to K.
Examples:
Input: S = β8642β, K = 2
Output: Yes
Explanation: Split the given string as {β8β, β6β, β4β, β2β}. Now, the difference between the consecutive substrings is K(= 2).Input: S = β1009896β, K = 0
Output: No
Approach: The given problem can be solved by generating all possible substring of the given string and check if the concatenation of any subset of the generated substring is equal to the given string S and the consecutive difference of the number as a substring is K, then print Yes. Otherwise, print No. Follow the below steps to solve the problem:
- Iterate over the range [1, N/2] using the variable i and perform the following steps:
- Store the substring of length i and starting from 0 in a variable X.
- Generate the sequence of size N starting with this number X where the difference of consecutive terms is K. Store this string in a variable test.
- If both the strings test and S are equal, then update the value of ans as true and break out of the loop.
- After completing the above steps, if the value of ans is false, print βNoβ. Otherwise, print βYesβ.
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 numeric string // can be split into substrings such that // the difference between the consecutive // substrings is K void isPossible(string s, int K) { bool valid = false ; long firstx = -1; // Stores the size of the string int n = s.length(); // Iterate over the range [1, N] and // try each possible starting number for ( int i = 1; i <= n / 2; ++i) { long x = stol(s.substr(0, i)); firstx = x; // Convert the number to string string test = to_string(x); // Build up a sequence // starting with the number while (test.length() < s.length()) { x -= K; test += to_string(x); } // Compare it with the // original string s if (test == s) { valid = true ; break ; } } // Print the result cout << ((valid == true ) ? "Yes " : "No" ); } // Driver Code int main() { string S = "8642" ; int K = 2; isPossible(S, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to check if a numeric String // can be split into subStrings such that // the difference between the consecutive // subStrings is K static void IsPossible(String s, int k) { boolean valid = false ; long firstx = - 1 ; // Stores the size of the String int n = s.length(); // Iterate over the range [1, N] and // try each possible starting number for ( int i = 1 ; i <= n / 2 ; ++i) { long x = Long.valueOf(s.substring( 0 , i)); firstx = x; // Convert the number to String String test = String.valueOf(x); // Build up a sequence // starting with the number while (test.length() < s.length()) { x -= k; test += String.valueOf(x); } // Compare it with the // original String s if (test.equals(s)) { valid = true ; break ; } } // Print the result System.out.println(valid ? "Yes" : "No" ); } // Driver code public static void main(String[] args) { String S = "8642" ; int K = 2 ; // Function call IsPossible(S, K); } } // This code is contributed by phasing17. |
Python3
# python 3 program for the above approach # Function to check if a numeric string # can be split into substrings such that # the difference between the consecutive # substrings is K def isPossible(s,K): valid = False firstx = - 1 # Stores the size of the string n = len (s) # Iterate over the range [1, N] and # try each possible starting number for i in range ( 1 ,n / / 2 + 1 , 1 ): x = int (s[ 0 :i]) firstx = x # Convert the number to string test = str (x) # Build up a sequence # starting with the number while ( len (test) < len (s)): x - = K test + = str (x) # Compare it with the # original string s if (test = = s): valid = True break # Print the result print ( "Yes" ) if valid = = True else print ( "No" ) # Driver Code if __name__ = = '__main__' : S = "8642" K = 2 isPossible(S, K) # This code is contributed by ipg2016107. |
C#
// C# program for the above approach using System; class GFG { // Function to check if a numeric string // can be split into substrings such that // the difference between the consecutive // substrings is K static void IsPossible( string s, int k) { bool valid = false ; long firstx = -1; // Stores the size of the string int n = s.Length; // Iterate over the range [1, N] and // try each possible starting number for ( int i = 1; i <= n / 2; ++i) { long x = Convert.ToInt64(s.Substring(0, i)); firstx = x; // Convert the number to string string test = x.ToString(); // Build up a sequence // starting with the number while (test.Length < s.Length) { x -= k; test += x.ToString(); } // Compare it with the // original string s if (test == s) { valid = true ; break ; } } // Print the result Console.WriteLine(valid == true ? "Yes" : "No" ); } // Driver code static void Main( string [] args) { string S = "8642" ; int K = 2; // Function call IsPossible(S, K); } } // This code is contributed by phasing17. |
Javascript
<script> // JavaScript program for the above approach // Function to check if a numeric string // can be split into substrings such that // the difference between the consecutive // substrings is K function isPossible(s, K) { let valid = false ; let firstx = -1; // Stores the size of the string let n = s.length; // Iterate over the range [1, N] and // try each possible starting number for (let i = 1; i <= n / 2; ++i) { let x = (s.substr(0, i)); firstx = x; // Convert the number to string let test = x.toString(); // Build up a sequence // starting with the number while (test.length < s.length) { x -= K; test += x.toString(); } // Compare it with the // original string s if (test == s) { valid = true ; break ; } } // Print the result document.write((valid == true ) ? "Yes " : "No" ); } // Driver Code let S = "8642" ; let K = 2; isPossible(S, K); </script> |
Yes
Time Complexity: O(N2)
Auxiliary Space: O(N)