Count the number of occurences of X's within a range in Java

Question

Given an integer X within the range of 0 to 9, and given two positive

integers as upper and lower bounds respectively, find the number of times X occurs as a digit in an integer within the range, excluding the bounds. Print the frequency of occurrence as output.

Input: The first line of input is an integer T, denoting the number of test cases. For each test case, there are two lines of input, first consisting of the integer X, whose occurrence has to be counted. Second, the lower and upper bound, L and U which are positive integers, on the same line separated by a single space, respectively.

Output: For each test case, there is only one line of output, the count of the occurrence of X as a digit in the numbers lying between the lower and upper bound, excluding them.

Constraints: 1<=T<=100 0<=X<=9 0

Example: Input 5 3 100 250 2 10000 12345 0 20 21 9 899 1000 1 1100 1345 Output: 35 1120 0 120 398

Explanation:

In the first test case, the occurrence of 3 in the numbers starting from 101 to 249 is counted and comes out to be 35.

My approach:

/*package whatever //do not write package name here */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class GFG {

    private static int numOccurences (int X, int low, int up)
        {
            String str;
            int totOcc = 0;

            //Convert a digit 0-9 to a character
            char chk = Character.forDigit(X,10);
            for (int i = low+1; i < up; i++)
                {
                    str = String.valueOf(i);
                    totOcc += numCharsInStr(str,chk);
                }
            return totOcc;
        }

    private static int numCharsInStr (String str, char ch)
        {
            int numOccurs = 0;
            for (int i = 0; i < str.length(); i++)
                {
                    if (str.charAt(i) == ch)
                        {
                            numOccurs++;
                        }
                }
            return numOccurs;
        }

    public static void main (String[] args) throws IOException {
        //code
        BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
        String line = br.readLine();
        String line2;
        String line3;

        int numTests = Integer.parseInt(line);
        int X;
        String [] inps;
        int lower;
        int upper;

        for (int i = 0; i < numTests; i++)
            {
                line2 = br.readLine();
                X = Integer.parseInt(line2);
                line3 = br.readLine();
                inps = line3.split(" ");
                lower = Integer.parseInt(inps[0]);
                upper = Integer.parseInt(inps[1]);
                System.out.println(numOccurences(X,lower,upper));
            }
    }
}

I have the following questions with regards to the code:

1. How can I further improve my approach?
2. Is there a better way to solve this question?
3. Are there any grave code violations that I have committed?
4. Can space and time complexity be further improved?

Reference

Answer 1

Here are my comments:

Find occurences of digit in String

Instead of iterating on every character, you can harness the power of regular expression. What we can do is replaceAll characters that are not the one we are interested in with an empty String effectively removing these characters and we are left with a String that contains all occurrences of the character.
For example, say we want to count occurrences of the digit 1 in str:

str.replaceAll("[^1]", "").length()

If you are concerned about performance, you should know that str.replaceAll() is a costly operation because the regex "[^1]" is parsed each time the method is called. This can be solved: you can parse the regex one time into an instance of java.util.regex.Pattern:

Pattern notDigitPattern = Pattern.compile("[^"+x+"]");  // x is the digit we want to count

This is done one time only. when you want to find occurences of x in str you do that by constructing an instance of java.util.regex.Matcher and using that to do the replaceAll() operation:

Matcher notDigitMatcher = notDigitPattern.matcher(str);
notDigitMatcher.replaceAll("").length()

Iteration on numbers

The 'main' loop iterates on the range of numbers between low and up. However, One can calculate in advance the number of occurences of any digit within range of 10 or 100 or 1000 and so on.
let us examine the range of 10. a digit will occur only once in that range except if it is the first digit as well.
The digit 3 apears once for 0x (0-9), 1x (10-19), 2x (20-29), and so on. it apears 11 times in 3x (30-39) 10 times as 1st digit and 1 time as 2nd.
sum of the above for all ranges of 10s (0-99) is 9*1+11=20. this is true for all 10 digits.
If we look at range of 100s than the digit will occur 20 times for all 100 ranges except if it is also the first digit, in this case add 100 occurrences.
sum of the above for all ranges of 100s (0-999) is 9*20+120=300.
you can continue this calculation for 1000s and so on.

When you receive an input of 111 to 3333 you know how many times the digit occurred between 1000 and 1999 and also 2000-2999. so you just need to iterate for the first and last 1000 (between 112 and 999 and 3000 to 3332) and you can also figure out complete 100 ranges. then figure out complete 10 ranges... at the end you will need to iterate on the first and last range of 10s.

I understand this seems unclear (and maybe too complicated) but it does save time complexity for large ranges.

Coding best practices

1. Closing IO resources
   although the stream you open on stdin will be closed when the program finishes, you should get the habbit of explicitly closing all resources, so yuo don't get resource leakage when you develop not-so-trivial programs. Use Java 7 try-with-resources feature for that.

2. Declare variables in the scope where they are used
   let's look at the variable inps in main(). It is used inside the loop as a kind if temporary variable for parsing the input. It is better to declare it inside the loop (each pair of curly braces define a new scope). There are two reasons for that: 1) declaring the variable inside the loop helps readability of your code - other developers will understand that inps is not used anywhere else. and 2) you don't run the risk of someone trying to use inps out of scope.

Answer 2

While I usually aggree with Sharon, in this case I'd say that using regex replacement for character counting is a bit over the top.

As usual, counting operations are already in place, you just have to know where you find them.

Given a string s and a character c to look for, consider this:

s.codePoints().filter(cp -> cp == c).count()

Very similarly, your main loop which calculates the sum could use the standard library, along the lines of:

IntStream.rangeClosed(firstNumber, lastNumber)
    .mapToObj(Integer::toString)
    .mapToInt(s -> numCharsInStr(s, myChar))
    .sum();