# Largest/Greatest of n numbers

Sudhir Srinivasan
Ranch Hand
Posts: 93

Hi,

The program takes input from the user,

- a number specifying the total size of the array[max. size 11 in this case]
- and the number for each array element,

sorts the numbers entered and writes to screen the greatest/largest number from them.

The code works just fine - output 1 below the code - when the array variable 'arr' is dimensioned with an index value [line no.10]. However, if the variable is declared as after taking the initial user input[value representing array size stored in num], the program executes upto the sorting part of the code but throws ArrayIndexOutOfBoundsException - kindly refer output 2 below the code - when encountering the comparison part of the program [lines 54-56].

Due to the array size dimensioned with a variable index value as opposed to with a static value, the for loop in lines 54-56 increments array element beyond the scope of the array thereby resulting in the above mentioned exception.

Could any of the experts suggest a workaround to this.

thanks,
Sudhir

output 1:
----------

init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
5
You have input: 5
Enter value:
5000
Value entered is: 5000
Enter value:
100
Value entered is: 100
Enter value:
350
Value entered is: 350
Enter value:
60
Value entered is: 60
Enter value:
400
Value entered is: 400
Numbers input sorted:
60
100
350
400
5000
Greatest of numbers input is: 5000
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
8
You have input: 8
Enter value:
1000
Value entered is: 1000
Enter value:
100
Value entered is: 100
Enter value:
300
Value entered is: 300
Enter value:
20
Value entered is: 20
Enter value:
90
Value entered is: 90
Enter value:
60
Value entered is: 60
Enter value:
45
Value entered is: 45
Enter value:
55
Value entered is: 55
Numbers input sorted:
20
45
55
60
90
100
300
1000
Greatest of numbers input is: 1000
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
0
BUILD SUCCESSFUL (total time: 58 seconds)

output 2:
----------
init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
4
You have input: 4
Enter value:
300
Value entered is: 300
Enter value:
50
Value entered is: 50
Enter value:
75
Value entered is: 75
Enter value:
20
Value entered is: 20
Numbers input sorted:
20
50
75
300
java.lang.ArrayIndexOutOfBoundsException: 4
at TestGreatestnNum.main(TestGreatestnNum.java:49)
BUILD SUCCESSFUL (total time: 16 seconds)

fred rosenberger
lowercase baba
Bartender
Posts: 12188
34
1) the best way to figure this out is to put System.out.println statements in your code.

2) the code you posted won't run:

C:\slop>java TestGreatestnNum
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
5
You have input: 5
Enter value:
java.util.InputMismatchException
at java.util.Scanner.throwFor(Unknown Source)
at java.util.Scanner.next(Unknown Source)
at java.util.Scanner.nextInt(Unknown Source)
at java.util.Scanner.nextInt(Unknown Source)
at TestGreatestnNum.main(TestGreatestnNum.java:29)

3) I'm not sure the code you posted matches the error/is what is being run. The error says the problem was on line 49, but line 49 of the code you posted is simply a closing brace.

Rob Spoor
Sheriff
Posts: 20613
63
The error Fred's getting can be solved by changing line 23 to use the actual line break, not \n. Fred's probably using Windows, which uses \r\n. That causes the \r to be part of the match, causing the number to not be an int.
Anyway, I tried it and never got an exception. There is a problem however; arr is defined to store at most 11 elements on line 10, and it's never changed afterwards. That means that your code will never allow more than 11 numbers. You can fix this by removing line 10, and adding the following line after line 20:
You'll then get another error for line 55 which is caused by j going up to num - 1 but you use j+1 inside the loop.

Ranch Hand
Posts: 312
You may do the following.
1. Move line number 10 to line number 24
2. Move line 54 below current line number 34
3. Comment or remove current lines 35 to 57
4. Add the following lines, after the current line number 57

Sudhir Srinivasan
Ranch Hand
Posts: 93

You may do the following.
1. Move line number 10 to line number 24
2. Move line 54 below current line number 34
3. Comment or remove current lines 35 to 57
4. Add the following lines, after the current line number 57

and the use of the predefined arrays class/sort method

1. Arrays.sort(arr);
2. result = arr[arr.length-1];

has certainly reduced my code length[sorting the numbers and then writing the result to screen] and also finds the greatest for any no. of values input.

Below is the modified code and its output.

regards,
Sudhir

output:
----------

init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
8
You have input: 8
Enter value:
3000
Value entered is: 3000
Enter value:
1500
Value entered is: 1500
Enter value:
500
Value entered is: 500
Enter value:
750
Value entered is: 750
Enter value:
900
Value entered is: 900
Enter value:
200
Value entered is: 200
Enter value:
50
Value entered is: 50
Enter value:
450
Value entered is: 450
Greatest of numbers input is: 3000
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
15
You have input: 15
Enter value:
300
Value entered is: 300
Enter value:
100
Value entered is: 100
Enter value:
200
Value entered is: 200
Enter value:
500
Value entered is: 500
Enter value:
150
Value entered is: 150
Enter value:
50
Value entered is: 50
Enter value:
75
Value entered is: 75
Enter value:
25
Value entered is: 25
Enter value:
40
Value entered is: 40
Enter value:
30
Value entered is: 30
Enter value:
80
Value entered is: 80
Enter value:
700
Value entered is: 700
Enter value:
35
Value entered is: 35
Enter value:
85
Value entered is: 85
Enter value:
90
Value entered is: 90
Greatest of numbers input is: 700
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
0
BUILD SUCCESSFUL (total time: 1 minute 23 seconds)

Rob Spoor
Sheriff
Posts: 20613
63
I wouldn't sort the array just to find the largest value. First of all, if this is a homework assignment, it probably defies the purpose of the assignment. Secondly, sorting is at least an O(n log n) operation, whereas a simple loop is an O(n) operation. That means that as the arrays grow larger, the simple loop becomes more and more efficient compared to the sorting.

If you don't know what O(n log n) and O(n) mean, please check out http://en.wikipedia.org/wiki/Big_O_notation.

Wouter Oet
Saloon Keeper
Posts: 2700
Since you only need the greatest value you could also just compare the previous value with the new value and store the greatest value.

Sudhir Srinivasan
Ranch Hand
Posts: 93

Rob Spoor wrote:First of all, if this is a homework assignment, it probably defies the purpose of the assignment.

The assignment was for finding the largest of 3 nos. For my learning, I extended the same by trying to find the largest of 'n' numbers input and therefore used the sorting.

Rob Spoor wrote:I wouldn't sort the array just to find the largest value.

Assuming array is dimensioned to 10 or 20 etc. and not num, without the sort, the for loop containing the comparison part of the code - result = arr[j] > arr[j+1] ? arr[j] : arr[j+1]; - would traverse the list only once comparing the previous array element with the current one and return the largest value for, say 3 numbers input, as shown

output 1:
------------
init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
3
You have input: 3
Enter value:
100
Value entered is: 100
Enter value:
50
Value entered is: 50
Enter value:
500
Value entered is: 500
Greatest of numbers input is: 500

If the array size grows to take in 7 values,

output 2:
-------------
init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
7
You have input: 7
Enter value:
1000
Value entered is: 1000
Enter value:
500
Value entered is: 500
Enter value:
700
Value entered is: 700
Enter value:
300
Value entered is: 300
Enter value:
150
Value entered is: 150
Enter value:
10
Value entered is: 10
Enter value:
600
Value entered is: 600
Greatest of numbers input is: 600
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
0
BUILD SUCCESSFUL (total time: 1 minute 3 seconds)

the comparison of arr[j] with arr[j+1] in this case returns 600 and not 1000 as the incrementor in the for loop moves the position of the previous and current array element such that,

for(int j = 0; j < num; j++) {

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[0] > arr[1] ? arr[0] : arr[1];
result = arr[0] containing 1000

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[1] > arr[2] ? arr[1] : arr[2];
result = arr[2] containing 700

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[2] > arr[3] ? arr[2] : arr[3];
result = arr[2] containing 700

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[3] > arr[4] ? arr[3] : arr[4];
result = arr[3] containing 300

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[4] > arr[5] ? arr[4] : arr[5];
result = arr[4] containing 150

result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
arr[5] > arr[6] ? arr[5] : arr[6];
result = arr[6] containing 600

}

Even if the array size is 3, the above logic returns the largest value as 75 instead of 300 for the following inputs (as opposed to 500 in output 1 as it happened to be the largest value of the array stored in array element arr[2] which is current value compared to previous value 50 of arr[1])

output 3:
------------

init:
deps-jar:
compile-single:
run-single:
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
3
You have input: 3
Enter value:
300
Value entered is: 300
Enter value:
50
Value entered is: 50
Enter value:
75
Value entered is: 75
Greatest of numbers input is: 75
Enter a value to specify no. of inputs(numbers) and find their greatest - 0 to exit:
0
BUILD SUCCESSFUL (total time: 22 seconds)

So, in the above 3 outputs, the absence of the for loops containing the sort

for(int i = 0; i < num; i++) { //for every pass
//In pass i, compare the first num-i elements with the next elements
for(int j = 0; j < num - 1; j++) {
if(arr[j] > arr[j+1]) { //comparison
int temp;
//swapping and ordering of elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

ensures there is only one traversal of list and no subsequent passes for comparison and sorting.

Note: In the above loops, I think I've made a mistake. variable 'i' should be initialized to 1 and not 0.

Rob Spoor wrote:Secondly, sorting is at least an O(n log n) operation, whereas a simple loop is an O(n) operation. That means that as the arrays grow larger, the simple loop becomes more and more efficient compared to the sorting.

-- Got it, the rate of increase in running time of the sort is directly proportional to the increase in the volume of input data [array size]. Considering the precedence of the orders of growth, O(n) is certainly more efficient to O(n log n). But since the sort is required, i guess O(n log n) is not too bad given its position in the big-O order of growth.

However, if there is still a way to avoid the sort with just the loop(s), please show the alternative.

Rob Spoor
Sheriff
Posts: 20613
63
A sort is definitely not required; finding the maximum in a List or array really only requires one single loop. But you must loop after you have all the values, and store the maximum of all elements you already inspected as an intermediate value:
As you see, a single loop, and at the end max will be the maximum value in the array. There is no need of comparing each element to any element except the maximum you found so far.

Campbell Ritchie
Sheriff
Posts: 49865
71
Sorting an array runs in at best O(nlogn) time and searching for the largest (or smallest) values runs in linear time = O(n)

If you still haven't got it working, I would make the following suggestions:
• 1: Forget what you have done to date.
• 2: Write down a series of numbers, and go through them by hand looking for the largest (or smallest) values.
• 3: Write down exactly what you are doing, in words of one syllable.
• 4: Now you have pseduocode, you can easily change that to real code
• Hint: When you only have one number n, the smallest number seen to date is n, and the lrgest number seen to date is n. When you have two different numbers, that will change.
Your while loop with while (number != 0) is a good way to proceed, as long as you are happy that 0 is a correct termination value.

Sudhir Srinivasan
Ranch Hand
Posts: 93

1. int max = -1; // assuming you only have positive numbers
2. for (int value: arr)
3. {
4. if (max < value) max = value;
5. }

certainly simplifies my earlier code and does away with the sort! As explained, from the single dimension array 'arr', each data element is copied and stored in 'value' and the largest of this compared to max.

# If you still haven't got it working, I would make the following suggestions:
1: Forget what you have done to date.
# 2: Write down a series of numbers, and go through them by hand looking for the largest (or smallest) values.
# 3: Write down exactly what you are doing, in words of one syllable.
# 4: Now you have pseduocode, you can easily change that to real code
Hint: When you only have one number n, the smallest number seen to date is n, and the lrgest number seen to date is n. When you have two different numbers, that will change.

also brought about the much needed clarity as i was confused with my own code!!

Campbell Ritchie
Sheriff
Posts: 49865
71
That for-each loop looks so much neater and more elegant, but I can see a possible enhancementThat means you start off guessing that the first value is the largest. You can do exactly the same for minimum; in fact it is probably best to do it in the same loop. You may wish to start with the subsequent values after my assignmentThat will give the correct values for any array size except a 0-length array, which will produce an ArrayOutOfBoundsException.

Sudhir Srinivasan
Ranch Hand
Posts: 93
Campbell Ritchie wrote:That for-each loop looks so much neater and more elegant, but I can see a possible enhancement

The suggested enhancement certainly works by initializing

which assumes the max and min values is the first array element.

Campbell Ritchie wrote:
That means you start off guessing that the first value is the largest. You can do exactly the same for minimum; in fact it is probably best to do it in the same loop. You may wish to start with the subsequent values after my assignmentThat will give the correct values for any array size except a 0-length array, which will produce an ArrayOutOfBoundsException.

So, for an array size of 4, the output is

max = 1000(arr[0])
min = 1000(arr[0])

arr[1] arr[2] arr[3]
1000 < 2000 2000 < 500 2000 < 750
max = 2000 max = 2000 max = 2000

1000 > 2000 1000 > 500 500 > 750
min = 1000 min = 500 min = 500

and for an array size of 10, the output is

max=500(arr[0])
min=500(arr[0])

arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] arr[9]
500 < 5000 5000 < 2500 5000 < 1000 5000 < 3200 5000 < 600 5000 < 450 5000 < 700 5000 < 225 5000 < 675
max = 5000 max = 5000 max = 5000 max = 5000 max = 5000 max = 5000 max = 5000 max = 5000 max = 5000

500 > 5000 500 > 2500 500 > 1000 500 > 3200 500 > 600 500 > 450 450 > 700 450 > 225 225 > 675
min = 500 min = 500 min = 500 min = 500 min = 500 min = 450 min = 450 min = 225 min = 225

many thanks,
Sudhir

Campbell Ritchie
Sheriff
Posts: 49865
71
You're welcome and you have finally got it working.