Largest/Greatest of n numbers

[Sudhir Srinivasan]

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

 int[] arr = new int[num];

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

import java.io.*;
import java.lang.*;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;

public class TestGreatestnNum {
     public static void main(String[] args) {
         int num;
         int[] arr = new int[11];
         
         //code segment to take user input
         System.out.println("Enter a value to specify no. of inputs" +
                 "(numbers) and find their greatest - 0 to exit: ");
         InputStreamReader isr = new InputStreamReader(System.in);
         Scanner scan = new Scanner(isr);
         
         try {
             while((num = scan.nextInt()) != 0) {
                 System.out.println("You have input: "+num);
                 
                 scan.useDelimiter("\n");
         
                 //code segment to take input of individual nos. randomly,store in respective array elements and print to screen
                 for(int i = 0; i < num; i++) {
                     System.out.println("Enter value: ");
                     new Scanner(isr);
                     
                     arr[i] = scan.nextInt();
                     System.out.println("Value entered is: "+arr[i]); 
                 }

                //sorting, in ascending order, of numbers input
                 for(int i = 0; i < num; i++) {
                   for(int j = 0; j < num - 1; j++)   {
                     if(arr[j] > arr[j+1])  {
                         int temp;
                         temp = arr[j];
                         arr[j] = arr[j+1];
                         arr[j+1] = temp;
                     }
                   }
                 }

                 //print on screen sorted numbers
                 System.out.println("Numbers input sorted: ");
                 for(int j = 0; j < num; j++) {
                     System.out.println(arr[j]);
                 }

                 //comparison of array elements
                //print result(greatest of numbers) on screen
                 int result = 0;
                 for(int j = 0; j < num; j++) {
                   result = arr[j] > arr[j+1] ? arr[j] : arr[j+1];
               }
                 System.out.println("Greatest of numbers input is: "+result);

         //take subsequent user input
         System.out.println("Enter a value to specify no. of inputs" +
                 "(numbers) and find their greatest - 0 to exit: ");
             }
         }catch(Exception e) {
             e.getMessage();
             e.printStackTrace();
         }finally {
            try {
                isr.close();
                scan.close();
            } catch (IOException ex) {
                Logger.getLogger(TestGreatestnNum.class.getName()).log(Level.SEVERE, null, ex);
            }
         }
    }
}

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]

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]

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.

scan.useDelimiter(System.getProperty("line.separator"));

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:

int[] arr = new int[num];

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.

[Madhan Sundararajan Devaki]

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

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

[Sudhir Srinivasan]

Thank you Madhan. Your suggestions

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

import java.io.*;
import java.lang.*;
import java.util.Scanner;
import java.util.Arrays;
import java.util.logging.Level;
import java.util.logging.Logger;

public class TestGreatestnNum1 {
    public static void main(String[] args) {
         int num;
         
         System.out.println("Enter a value to specify no. of inputs" +
                 "(numbers) and find their greatest - 0 to exit: ");
         InputStreamReader isr = new InputStreamReader(System.in);
         Scanner scan = new Scanner(isr);
         
         try {
             while((num = scan.nextInt()) != 0) {
                 System.out.println("You have input: "+num);
                 
                 scan.useDelimiter("\n");
                 
                 int[] arr = new int[num];
                 
                 for(int i = 0; i < num; i++) {
                     System.out.println("Enter value: ");
                     new Scanner(isr);
                     
                     arr[i] = scan.nextInt();
                     System.out.println("Value entered is: "+arr[i]); 
                 }
                 for(int i = 0; i < num; i++) {
                   for(int j = 0; j < num; j++) {
                  }
                }
                 Arrays.sort(arr);
                 int result = arr[arr.length-1];
                 System.out.println("Greatest of numbers input is: "+result);
         System.out.println("Enter a value to specify no. of inputs" +
                 "(numbers) and find their greatest - 0 to exit: ");
          }
         }catch(Exception e) {
             e.getMessage();
             e.printStackTrace();
         }finally {
            try {
                isr.close();
                scan.close();
            } catch (IOException ex) {
                Logger.getLogger(TestGreatestnNum.class.getName()).log(Level.SEVERE, null, ex);
            }
         }
    }
}

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]

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]

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]

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]

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:

int max = -1; // assuming you only have positive numbers
for (int value: array)
{
    if (max < value) max = 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]

Have you really read all the answers you have been given?
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]

Thank you Rob for your patience and answers. Your enhanced for loop

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.

Thank you Campbell, your suggestions

# 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]

That for-each loop looks so much neater and more elegant, but I can see a possible enhancement

   int max = arr[0]; 

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 assignment

for (int i = 1; i < arr.length; a++)
{
    if (max < arr[i])
    {
        max = arr[i];
    }
    if (min > arr[i])
    {
        min = arr[i];
    }
}

That will give the correct values for any array size except a 0-length array, which will produce an ArrayOutOfBoundsException.

[Sudhir Srinivasan]

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

   int max = arr[0]; 

The suggested enhancement certainly works by initializing

int max = arr[0];
int min = arr[0];

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 assignment

for (int i = 1; i < arr.length; a++)
{
    if (max < arr[i])
    {
        max = arr[i];
    }
    if (min > arr[i])
    {
        min = arr[i];
    }
}

That 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

init:
deps-jar:
compile-single:
run-single:
Enter a number specifying number of inputs and to find their maximum/minimum value(0 to exit): 
4
You have input: 4
Enter a value: 
1000
Value entered is: 1000
Enter a value: 
2000
Value entered is: 2000
Enter a value: 
500
Value entered is: 500
Enter a value: 
750
Value entered is: 750
Maximum value is: 2000
Minimum value is: 500

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

Enter a number specifying number of inputs and to find their maximum/minimum value(0 to exit): 
10
You have input: 10
Enter a value: 
500
Value entered is: 500
Enter a value: 
5000
Value entered is: 5000
Enter a value: 
2500
Value entered is: 2500
Enter a value: 
1000
Value entered is: 1000
Enter a value: 
3200
Value entered is: 3200
Enter a value: 
600
Value entered is: 600
Enter a value: 
450
Value entered is: 450
Enter a value: 
700
Value entered is: 700
Enter a value: 
225
Value entered is: 225
Enter a value: 
675
Value entered is: 675
Maximum value is: 5000
Minimum value is: 225
Enter a number specifying number of inputs and to find their maximum/minimum value(0 to exit): 
0
BUILD SUCCESSFUL (total time: 1 minute 55 seconds)

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]

You're welcome and you have finally got it working.