# “Chef and Digits” Java solution

I am looking for a review on the following code which is for this question. I am looking for a general review of the code. I am specifically also looking for advice on how to make this code run more efficiently.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
public class Main
{
public static void main(String args[]) throws IOException
{
int S[] = new int[100000];
PrintWriter out = new PrintWriter(System.out);
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
char num[] = St.toCharArray();
for (int j = 0; j < m; j++)
{
int r = Integer.parseInt(r1);
int sum1 = 0, sum2 = 0;
for (int p = 0, len = num[r - 1]; p < r - 1; p++)
{
int diff = len - num[p];
if (diff < 0)
sum1 = sum1 + diff;
else
sum2 = sum2 + diff;
}
out.println((sum2 - sum1));
}
out.flush();
out.close();
}
}

• This looks like it is a C program. It's not bad in itself, but you probably don't want to write something like this for a Java job interview. – toto2 Apr 8 '14 at 19:37

Naming Conventions
Variables in java should be camelCase, meaning they should start with a small letter.

Meaningful names
Someone reading your code doesn't stand a chance in hell to understand what you are trying to do without actually running this code in his head...
Your class is called Main, your only method is main... at least try to tell your reader some story on what you are trying to do, especially when you post it for review!
Variable names like n, m, num, and sum add nothing to explain your code. Names like s and S are even worse.

Efficiency
It is very hard to give efficiency advice, if I can't say what exactly you are trying to achieve, but some obvious observations:

int S[] = new int[100000];


This doesn't look very efficient - you allocate all this memory up front, and I couldn't really see where you are using it...

Your is also not very defensive - you don't close your stream in case of an exception (you should use try(PrintWriter out = new PrintWriter(System.out)) block to make sure of that), and you never validate that num[r - 1] is valid, so there is a decent chance that your code will not run as expected.

Idioms
You should use the idioms relevant for the language you use, for example - sum1 += diff; instead of sum1 = sum1 + diff;
Another example - don't wrap System.out with PrintWriter simply use System.out.println(sum2 - sum1)

• @ Uri Aggasi the code is giving output on expected lines,But I keep getting Time Limit Exceeded issue,that array declaration in needless,iam fine with that,is der any way to avoid the iterative loops and get to the answer in a single expression,any specific algorithm I mean? – arunkrishnamurthy01 Apr 8 '14 at 18:21
• I can't tell you, because I can't understand what your code does. I suggest that you edit your post, add some description on what you are trying to do, with example input and output. – Uri Agassi Apr 8 '14 at 18:24
• codechef.com/APRIL14/problems/ADIGIT Refer this link for Problem Statement and Sample input output – arunkrishnamurthy01 Apr 8 '14 at 18:53
• @arunkrishnamurthy01 Uri isn't asking what the problem statement is, Uri is telling you that it is too much effort to try to understand what your code does. Without understanding what your code does it is not possible to offer suggestions on how to improve it. Make your existing code easier to understand and people will be more willing to help you improve it. – Mike B Apr 8 '14 at 19:09

First of all, it's important to decompose the problem to its elementary steps, for example:

• Parse the input
• Do the calculation

In your program everything is in a single method: the problem is not decomposed well. You should decompose at least to these items, and possibly further decompose the calculation.

In a quiz like this, if performance is the problem, it's usually all because of the calculation. So I'll focus on that part only. After you decomposed the problem, you should end up with a method like this:

private int doCalculation(int[] digits, int index) {
int sum = 0;
// TODO
return sum;
}


That is, a method that takes the digits you parsed, and the index you parsed, and the method should calculate the answer. As a next step, it's good to create unit tests based on the given examples to check your solution, for example:

@Test
public void testExamples() {
int[] digits = new int[] {0, 3, 2, 4, 1, 5, 2, 3, 9, 7};
Assert.assertEquals(0, doCalculation(digits, 1));
Assert.assertEquals(7, doCalculation(digits, 4));
Assert.assertEquals(9, doCalculation(digits, 7));
}


I simply added the tests from the problem description. If you can think of corner cases not covered by these examples, you should add them too.

Next, you can implement the calculation using a naive logic that might be inefficient, but serve as a good proof of concept, especially for corner cases. For example, a simplified version of yours, but probably still inefficient:

private int doCalculation(int[] digits, int index) {
int sum = 0;
for (int i = 0; i < index - 1; ++i) {
sum += Math.abs(digits[index - 1] - digits[i]);
}
return sum;
}


Once that's done you can move on to refactoring the calculation logic, try to make it more efficient without breaking the unit tests.

As for making it more efficient... Off the top of my head: the current naive implementation might recalculate sums too many times unnecessarily. Consider the case when digits[X-1] == digits[Y-1] for X < Y. If we already called doCalculation(digits, X), then doCalculation(digits, Y) will unnecessary calculate sums for digits[0] ... digits[X-1]. It would be better to reuse the result of the previously calculated doCalculation(digits, X), and add to that the sums for digits[X] ... digits[Y-1].

I hope this helps, and good luck!