Count number of substrings with numeric value greater than X in C++

We are given a string of numbers 0 to 9. The string represents a decimal number. The goal is to find all substrings that represent a decimal number which is greater than number X. Condition is that substring should not start with 0. I.e in “2021”, “02”, “021”. “0” will not be included.

We will do this by checking the first value of all substrings, if it is greater than 0 then start making substrings from that index by converting them into integers using stoi(). If substring>X increment count.

Let us understand with examples.

Input − str=”123” X=12

Output − Count of number of substrings with numeric value greater than X are − 2

Explanation Substrings > 12 are 123 and 23.

Input − str=”111” X=100

Output − Count of even decimal value substrings in a binary string are − 1

Explanation Only 111 is greater than 100.

Approach used in the below program is as follows

• We take a string str as a string of numbers only.

• Store the length of str in len=str.length()

• Function greater_X(string str, int x) takes the string and its length and returns a count of substrings that form a decimal number greater than X.

• Traverse string using FOR loop

• Starting from index i=0 to i<len, reading from left to right.

• If any str[i]!=’0’ means all substrings starting from it will be valid.

• Starting from index j=1 to i+j<len, for length of substring.

• Convert substring str.substr(i,j) to decimal using stoi(). If it is more than X. Increment count.

• Return count as result.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int greater_X(string str, int x){    int count = 0;    int len = str.length();    for (int i = 0; i < len; ++i){       if(str[i] != '0'){          for (int j=1; (i + j) <= len; ++j){             if (stoi(str.substr(i, j)) > x){                count++;             }          }       }    }    return count; } int main(){    string str = "987";    int x = 100;    cout<<"Count of number of substrings with numeric value greater than X are: "<<greater_X(str, x);    return 0; }

Output

If we run the above code it will generate the following output −

Count of number of substrings with numeric value greater than X are: 1