NOTICE ISP is back up.. Stay tuned for class status for Thursday 2017-03-23
Free Java Tutorials >> Table of contents >> Array Algorithms

1. Summation

Sum the numbers in an array:

Like our previous loop algorithms, we need to create an int sum before the loop scope:

public class MyProgram {
    public static void main(String[] args) {
		int[] b = {123,234,345,456};
		
		//Begin summing
		int sum = 0;
		for(int i = 0; i < b.length ; i++) { 
			sum += b[i];
		}
		
		System.out.println("The sum is:");
		System.out.println(sum); //prints 1158
    }
}

Create an array with the perfect squares from 1 to 10, then sum them:

Now that we have a summation algorithm done, we can write code to generate an array and sum it:

public class MyProgram {
    public static void main(String[] args) {
		int[] b = new int[10]; //empty array of size 10
		for(int i = 0; i < b.length ; i++) { 
			b[i] = (i+1)*(i+1); //b[0] = 1*1, b[1] = 2*2, b[2] = 3*3;
		}
		
		//Begin summing
		int sum = 0;
		for(int i = 0; i < b.length ; i++) { 
			sum += b[i];
		}
		
		System.out.println("The sum is:");
		System.out.println(sum); //prints 385
    }
}


			
Run

2. Filtering

Print all even numbers in an array

To filter an array, we perform an action on elements that match a condition. This requires an if statement inside a loop:

public class MyProgram {
    public static void main(String[] args) {
		int[] b = {123,234,345,456};
		
		for(int i = 0; i < b.length ; i++) { 
			if(b[i] % 2 == 0) { //if b[i] is even
				System.out.println(b[i]); //print it
			}
		}
		//This program prints 234 and then 456
    }
}

Print all prime numbers in an array

This is a more complicated algorithm. We need to check each number in an array and see if it is prime. A pseudo algorithm may look like:

//Given array x
//Loop through each element 'e' in x:
//   Assume e is prime
//   Loop through each number 'j' between 2 and the square root of e. 
//       If e divides any of 'j' evenly, then e is not prime
//   If e is prime, print it

Let's look at this in code:

public class MyProgram {
    public static void main(String[] args) {
		int[] x = {42,1303,1323,1171,1031,1131,2430,683};
		
		for(int i = 0; i < x.length ; i++) { 
			//we called x[i] e in the pseudo code
			boolean isPrime = true;
			for(int j = 2; j*j <= x[i] ; j++) {
				if(x[i] % j == 0) {
					isPrime = false;
				}
			}
			if(isPrime) {
				System.out.println(x[i]); //print it
			}
		}
		//This program prints 1303,1171,1031, and 683
    }
}

Sum all prime numbers in an array

This is actually just a small addition to the previous algorithm. We need to add into an int sum declared before the outer loop:

public class MyProgram {
    public static void main(String[] args) {
		int[] x = {42,1303,1323,1171,1031,1131,2430,683};
		
		int sum = 0; //the sum variable
		for(int i = 0; i < x.length ; i++) { 
			boolean isPrime = true;
			for(int j = 2; j*j <= x[i] ; j++) {
				if(x[i] % j == 0) {
					isPrime = false;
				}
			}
			if(isPrime) {
				sum += x[i];
			}
		}
		System.out.println(sum);
		//This program prints 4188
    }
}

Note that we can collapse the blocks. The previous program might be written as this, and it has the same behavior:

public class MyProgram {
    public static void main(String[] args) {
		int[] x = {42,1303,1323,1171,1031,1131,2430,683};
		
		int sum = 0; 
		for(int i = 0; i < x.length ; i++) { 
			boolean isPrime = true;
			for(int j = 2; j*j <= x[i] ; j++) if(x[i] % j == 0) isPrime = false;
			if(isPrime) sum += x[i];
		}
		System.out.println(sum);
		//This program prints 4188
    }
}


			
Run

3. Min/Max

Print the maximum value in an array

What we can do is assume that the first value is the largest. We will store this in a variable called "max". Then, we will traverse the array. If any value is larger than the max, then that should be the new max:

public class MyProgram {
    public static void main(String[] args) {
		int[] x = {42,1303,1323,1171,2,1031,1131,2430,683};
		
		int max = x[0];
		for(int i = 1; i < x.length ; i++) { 
			if(x[i] > max) max = x[i];
		}
		System.out.println(max); //prints 2430
    }
}

Print the minimum index in an array

One way we could find the minimum is simply flip the greater than in the previous if statement into a less than. In this example, we will make another change. Rather than storing min equal to the first element, we will store min to be the first index, 0. Then, when we make comparisons with the min, we need to retrieve the value at that index:

public class MyProgram {
    public static void main(String[] args) {
		int[] x = {42,1303,1323,1171,2,1031,1131,2430,683};
		
		int minIndex = 0;
		for(int i = 1; i < x.length ; i++) { 
			if(x[i] < x[minIndex]) minIndex = i;
		}
		//Now minIndex is the index of the smallest item
		System.out.println("The minimum index is:");
		System.out.println(minIndex);    //prints 4
		System.out.println("The value at that index is:");
		System.out.println(x[minIndex]); //prints 2
    }
}

Print the maximum prime in an array

We want to find the maximum prime in an array. Unfortunately, we cannot use the previous max example, because there is a possibility that no numbers are prime. Thus, we will store the index of the max prime in an integer, and we will initialize that index to -1:

public class MyProgram {
    public static void main(String[] args) {
		int[] x = {42,1303,1323,1171,2,1031,1131,2430,683};
		
		int maxIndex = -1; //This is an index here
		for(int i = 0; i < x.length ; i++) { 
			//first let's check if the number is prime:
			boolean isPrime = true;
			for(int j = 2; j*j <= x[i] ; j++) {
				if(x[i] % j == 0) {
					isPrime = false;
				}
			}
			if(isPrime) {
				//Now let's check if it is bigger than the max
				//OR there was no previous max:
				if(maxIndex == -1 || x[i] > x[maxIndex]) {
					maxIndex = i;
				}
			}
		}
		if(maxIndex == -1) {
			System.out.println("There are no primes");
		}else {
			System.out.println("The maximum index is:");
			System.out.println(maxIndex);    //prints 1
			System.out.println("The value at that index is:");
			System.out.println(x[maxIndex]); //prints 1303
		}
    }
}


			
Run

5. Double Loops

Subset sum of size 2

We want to check if any two numbers in int[] x add up to 42. This is a special case of the "subset sum problem", which in this case is solvable with two loops. The "subset" is the pair of two numbers. Note that we would require three loops for subsets of size 3, four loops for subsets of size four, etc. A general solution for subsets of any size is a more advanced algorithm, which advanced students can find in the section on recursion. Here we use the first loop to try every possible first number, and the second loop to try every possible second number:

public class MyProgram {
    public static void main(String[] args) {
		int[] x = {10,12,20,30};
		int target = 42;
		for(int i = 1; i < x.length; i++) { //we could start with i=0, but using 1 makes it slightly faster
			for(int j = 0; j < i ; j++) {     //we could do less than x.length, but that would repeat pairs
				if( x[i]+x[j] == 42 ) { //we would need to check i!=j if we didn't do j < i
					System.out.println("possible");  //we could store this in a boolean if we only wanted to output once
				} //we could break in this if statement if we wanted to find the first one only
			}
		}
    }
}

Largest subset of size 2 under maxSum

In this problem, we want to pick two numbers so that they get as close to maxSum as possible without going over:

public class MyProgram {
    public static void main(String[] args) {
		int[] y = {5,10,12,20,30}; 
		int maxSum = 28; //best will be 25
		int best = 0;
		for(int i = 1; i < y.length; i++) {
			for(int j = 0; j < i; j++) {
				if( y[i]+y[j] <= maxSum && y[i]+y[j] > best ) {
					best = y[i]+y[j];
				}
			}
		}
		System.out.println(best);
    }
}

Like the previous algorithm, we loop over each possible pair. To avoid pairs where the first item and the second item are the same, we make j less than i. Then, we use an if statement to check whether we've found a better pair, and store that in best



			
Run

Previous: Arrays

Next: Two Dimensional Arrays