trjhtr

My algorithm works but it is too slow.

I have to ask for help with improving this algorithm because the website which checks this, kicks me for too slow execution.

What should I improve here ?

Details:

Given a sequence of 2*k characters, please print every second
character from the first half of the sequence. Start printing with the
first character.

Input In the first line of input your are given the positive integer t
(1<=t<=100) - the number of test cases. In the each of the next t
lines, you are given a sequence of 2*k (1<=k<=100) characters.

Output For each of the test cases please please print every second
character from the first half of a given sequence (the first character
should appear).

Example

Input:

4
your
progress
is
noticeable

Output:

y
po
i
ntc 

class Chars

 public static void main (String args) 

 Scanner sc = new Scanner(System.in);
 int t = sc.nextInt();
 if (t <= 100 && t >= 1) 
 for (int i = 0; i < t; i++) 
 calculate();
 
 
 

 private static void calculate() 

 Scanner sc = new Scanner(System.in);
 String rawString = sc.nextLine();
 StringBuilder afterAdd = new StringBuilder();
 StringBuilder finishChars = new StringBuilder();
 int numberOfChars = rawString.length();
 if (numberOfChars <= 100 && numberOfChars >= 1) 
 if (numberOfChars % 2 == 0) 
 int numHalfChars = numberOfChars / 2;
 for (int i = 0; i < numHalfChars; i++) 
 afterAdd.append(rawString.charAt(i));
 
 if (afterAdd.length() <= 2) 
 System.out.println(afterAdd.charAt(0));
 else 
 for (int i = 0; i < afterAdd.length(); i = i + 2) 
 finishChars.append(afterAdd.charAt(i));
 
 System.out.println(finishChars);
 
 
 
 

after improve:

class Algorithm

 private static List<String> results = new ArrayList<>();

 public static void main (String args) 
 calculate();
 show();
 

 private static void show() 
 for (String result : results) 
 System.out.println(result);
 
 

 private static void calculate() 
 Scanner sc = new Scanner(System.in);
 int t = sc.nextInt();
 if (t <= 100 && t >= 1) 
 for (int i = 0; i <= t; i++) 
 String rawString = sc.nextLine();
 StringBuilder finishChars = new StringBuilder();
 int numberOfChars = rawString.length();
 if (numberOfChars <= 100 && numberOfChars >= 1 && numberOfChars % 2 == 0) 
 for (int j = 0; j < rawString.length() / 2; j = j + 2) 
 finishChars.append(rawString.charAt(j));
 
 results.add(String.valueOf(finishChars));
 
 
 
 

Your code is slow simply because it does much more than it needs to. It copies the first half of the original string to a new StringBuilder, but then, you only use this StringBuilder to access its characters by their index, which you could also do with the original string, since the indexes of the characters in the first half of the original string and those in this new StringBuilder are identical.

So you might as well omit the variable afterAdd and use the original string in its place when you iterate over every second character:

for (int i = 0; i < rawString.length() / 2; i = i + 2) 
 finishChars.append(rawString.charAt(i));

Also, there is no need to handle the case afterAdd.length() <= 2 (which, after deleting afterAdd, would translate to rawString.length() <= 4) separately. The result of the method will be unaffected if you remove this extra if and simply let the for loop take care of it. In fact, I don't see anything special in this case in the first place, so I wonder why you make a special case for it.

Besides, I think it is strange that you let the main method read the number of test cases from the command line, but delegate the reading of the individual test cases to the calculate method, not least because this requires you to create a new Scanner object for every single test case. Why don't you do all the reading from the command line in one method, and then pass each test case to the method calculate as a parameter and let it do only do what its name suggest, namely calculating the result?

Anyway, I would suggest separating user interface from program logic, because right now, the method calculate not only calculates the result, but also prints it to System.out, which goes a bit against the Single Responsibility Principle. I think the code would be clearer if calculate returns a String representing the result, so that the calling method can decide what to do with the result.

• It's a better practice to return the List of results rather than making it a class varible.




• You still have IO tied into your program logic. You just moved it.




• There's some disagreement on whether or not it's appropriate to close a Scanner. I think it's a good idea.




• Your bounds checking is noise. The problem description is telling you those are the invariants. You don't need to check them.




• You do indeed have a logic error. You need to call nextLine() after nextInt() and before entering your looping code. The scanner cursor is sitting on the first line after the 4 after you call nextInt(), and so your first nextLine() in the loop is returning an empty String. You wind up missing the last word because of that.




• For raw speed, you can try replacing the StringBuilder with a char. You can also try using shift operators instead of division/multiplication by 2. The compiler may make these optimizations under the covers, so this may do nothing, and they makes the code a lot harder to read. Avoid them unless you need them. Usually performance problems at these kinds of websites require algorithmic fixes, not micro-optimizations.

If you made all these changes, your code might look something like:

class Algorithm 

 public static void main(final String args) 
 try (final Scanner scanner = new Scanner(System.in)) 
 final int wordCount = scanner.nextInt();
 scanner.nextLine();
 /*
 for (int i = 0; i < wordCount; i++) 
 System.out.println(calculate(scanner.nextLine()));
 
 */
 for (int i = 0; i < wordCount; i++) 
 for (final char c : calculate2(scanner.nextLine())) 
 System.out.print(c);
 
 System.out.println();
 

 catch (final Exception e) 
 System.err.println(e.getMessage());
 
 

 private static String calculate(final String word) 
 final StringBuilder result = new StringBuilder();
 for (int i = 0; i < (word.length() / 2); i += 2) 
 result.append(word.charAt(i));
 
 return result.toString();
 

 private static char calculate2(final String word) 
 final int bonus = ((word.length() % 4) == 0) ? 0 : 1;
 final int arraySize = (word.length() >> 2) + bonus;
 final char letters = new char[arraySize];

 for (int i = 0; i < letters.length; i++) 
 letters[i] = word.charAt(i << 1);
 

 return letters;