3
\$\begingroup\$

The input begins with the number \$t\$ of test cases in a single line (\$t \le 10\$). In each of the next t lines there are two or more numbers \$m\$ and \$n\$ (\$1 \le m \le n \le 1000000000\$, \$n-m \le 100000\$) separated by a space.

Print each number in a separate line which can be used further for summation.

Input

2

50 100

100 50 105

Output

50

100

100

50

105

This is the code that I've written that is giving me output:

import java.util.Scanner;
import java.util.StringTokenizer;

public class Generation {

    public static void main(String[] str) {

        Scanner keyboard = new Scanner(System.in);
        int inputSize;
        do {
            System.out.println("Enter the value of T Size");
            inputSize = keyboard.nextInt();
            keyboard.nextLine();
            if (inputSize < 2 || inputSize > 10) {
                System.out.println("Not a Valid Input Size");
            }
        } while (inputSize < 2 || inputSize > 10);

        String[] inputValue = new String[inputSize];
        int tokenCount = 0;
        for (int i = 0; i < inputSize; i++) {
            System.out.println("Enter the inputs");
            inputValue[i] = keyboard.nextLine();
            StringTokenizer strToken = new StringTokenizer(inputValue[i], " ");
            tokenCount += strToken.countTokens();
        }
        keyboard.close();

        //suppose this is 2nd part 
        int[] splitedString = new int[tokenCount];
        int tempTokenCount = 0;
        for (int i = 0; i < inputSize; i++) {
            String[] tempSplitArray = inputValue[i].split(" ");
            for (int j = 0; j < tempSplitArray.length; j++) {
                splitedString[tempTokenCount] = Integer
                        .parseInt(tempSplitArray[j]);
                tempTokenCount++;
            }

        }
        /*for (String s : inputValue) {
            System.out.println(s);
        }*/
        for (Integer s : splitedString) {
            System.out.println(s);
        }

    }

}

How can I optimize the 2nd part where I have to use two for loop which result in \$O(n^2)\$ time complexity? What is the workaround for such situations?

\$\endgroup\$
3
  • 3
    \$\begingroup\$ The result of the for-loop is not O(n^2), it is actually O(n). A nested for-loop does not always equate to O(n^2) time complexity. I think you might be looking for a way to do the entire thing in one loop which is what JShade01 has provided \$\endgroup\$
    – smac89
    May 15, 2015 at 5:26
  • 1
    \$\begingroup\$ Huh, I don't understand the challenge. It is unclear to me. \$\endgroup\$
    – rolfl
    May 15, 2015 at 11:11
  • \$\begingroup\$ @rolfl OP didn't post the challenge, he simply was asking of a way to convert all the inputs to integers \$\endgroup\$
    – smac89
    May 15, 2015 at 17:34

2 Answers 2

6
\$\begingroup\$

try-with-resources

If you're on Java 7, you should use try-with-resource on your Scanner:

try (Scanner scanner = new Scanner(System.in)) {
    // your code here
}

This takes care of closing your Scanner at the end, so you do not have do perform an explicit close().

First input

I am not too sure why are you ensuring inputSize cannot be less than 2, since the problem statement only mentioned <= 10. I'll take that to mean an implicit assumption for non-negative values, so yeah even 0 is possibly a valid input. There is also an easier way of getting your first input than performing your validation twice, and while you're at that you should consider putting it in a method:

private static int getCount(Scanner scanner) {
    System.out.println("Enter the value of T Size [0, 10]:");
    int value = scanner.nextInt();
    while (value < 0 || value > 10) {
        System.out.println("Value is not within [0, 10], try again.");
        value = scanner.nextInt();
    }
    scanner.nextLine(); // gotcha
    return value;
}

The gotcha, as you probably have already figured, is that you need to 'consume' the rest of the line first before moving to other inputs. Therefore, I will also suggesting reading as nextLine() instead and then attempt to convert to an int via Integer.parseInt(). You can then catch the NumberFormatException thrown as an invalid input, and re-prompt until a valid integer is entered.

Validating your additional inputs

Note: I'm not sure if integers are implied for numbers, so I'll just go along with what you have shown...

First, I think you are missing the validation on your integers-to-be:

\$m\$ and \$n\$ (\$1 \le m \le n \le 1000000000\$, \$n-m \le 100000\$)

Second, you should also consider converting and saving each of the integers you encounter in a single input line immediately, instead of storing into a String[] array and then performing the conversion afterwards. This avoids the additional looping which you identified in your question. :)

Come and think of it, putting all these together does sound like a good usage for Java 8 streams...

Java 8 solution ahead

So to conclude, the steps we need are:

  1. Get number of lines (0 <= x <= 10)

    stream.limit(getCount(scanner))
    

    We only read in this number of lines, x = getCount(scanner).

  2. Read in a line for x times

    Stream.generate(scanner::nextLine)
    

    This creates a new stream where each element is read from the scanner, i.e. System.in, i.e. the user input. This is accessed via a method reference.

  3. On each line, split by a ' ' character

    stream.flatMap(Pattern.compile(" ")::splitAsStream)
    

    Pattern.splitAsStream(CharSequence) is a convenient way of tokenizing a line as a stream, which in turn allows us to perform a flatMap() by replacing each element of the source stream with the contents of the resulting stream.

  4. Convert each token as an integer within a certain range

    stream.map(Generation::convert)
    

    The sample implementation shown below for convert(String) does not perform any validation. Actually, as a result of the flatMap() operation in the previous step, it will be quite tricky to make sure that \$1 \le m \le n \le 1000000000\$, so I'll leave this as an exercise to the reader... (hint: map each String input as a List to facilitate the validation first).

  5. Collect all results into a Collection for further usage

    stream.filter(Objects::nonNull).collect(Collectors.toList())
    

    Since convert(String) may give us null values for invalid integers, we need to exclude them first. Collecting as toList() is just for illustration. If you want to sum the results together immediately, for example, you can change that to .mapToInt(Integer::intValue).sum().

public class Generation { // you probably need a better name too
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            List<Integer> result = Stream.generate(scanner::nextLine)
                    .limit(getCount(scanner))
                    .flatMap(Pattern.compile(" ")::splitAsStream)
                    .map(Generation::convert)
                    .filter(Objects::nonNull)
                    .collect(Collectors.toList());
            result.forEach(System.out::println);
        }
    }

    private static int getCount(Scanner scanner) {
        // see implementation above
    }

    private static Integer convert(String value) {
        try {
            return Integer.valueOf(value);
        } catch (NumberFormatException e) {
            return null;
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

If you looking for a shorter solution, here is one:

You can change your initial for-loop to just two lines like so:

String content = new Scanner(System.in).useDelimiter("\\Z").read();
StringTokenizer tokens = new StringTokenizer(content);

Then your next set of loops can be changed to just one which will simply loop through all the tokens in the tokenizer and parse each string into an integer using integer.parseInt

while (tokens.hasMoreTokens()) {
    // parse a token and store in an array
}

Note this assumes that the rest of the tokens in stdin are integers, therefore it might fail if there are any non integers

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.