Chapter 6 Programming Exercise Solutions
P6.1
public class ArrayPrinter
{
public static void main(String[] args)
{
int[] data = new int[10];
for (int i = 0; i < 10; i++)
{
data[i] = (int) (Math.random() * 100 + 1);
}
// Print out even indices
for (int i = 0; i < data.length; i = i + 2)
{
System.out.print(data[i] + " ");
}
System.out.println();
// Print out even elements
for (int i = 0; i < data.length; i++)
{
if (data[i] % 2 == 0)
{
System.out.print(data[i] + " ");
}
}
System.out.println();
// Print out elements in reverse order
for (int i = data.length - 1; i >= 0; i--)
{
System.out.print(data[i] + " ");
}
System.out.println();
// Print out only first and last element
System.out.printf("%d %d\n", data[0], data[data.length - 1]);
}
}
P6.2
Array methodsthat do the following:
a) Swap first and last elements in an array.
public static void swapFirstLast(int[] arr)
{
int last = arr.length - 1;
int temp = arr[0];
arr[0] = arr[last];
arr[last] = temp;
}
public static void main(String[] args)
{
int[] randoms = new int[10];
// Create a test array containing random numbers.
for (int i = 0; i < 10; i++)
{
randoms[i] = (int) (Math.random()*100) + 1;
// Print the values as they are assigned.
System.out.print(randoms[i] + " ");
}
System.out.println();
// Perform the swap.
swapFirstLast(randoms);
// Print again to see new order.
for (int i = 0; i < 10; i++)
{
System.out.print(randoms[i] + " ");
}
System.out.println();
}
b) Shift all elements by one to the right.
public static void rotateRight(int[] arr)
{
int last = arr.length - 1;
int temp = arr[last];
for (int i = last; i > 0; i--)
{
arr[i] = arr[i - 1];
}
arr[0] = temp;
}
public static void main(String[] args)
{
int[] randoms = new int[10];
// Create a test array containing random numbers.
for (int i = 0; i < 10; i++)
{
randoms[i] = (int) (Math.random() * 100) + 1;
// Print the values as they are assigned.
System.out.print(randoms[i] + " ");
}
System.out.println();
// Rotate the array once to the right.
rotateRight(randoms);
// Print again to see new order.
for (int i = 0; i < 10; i++)
{
System.out.println(randoms[i] + " " );
}
System.out.println();
}
c) Replace all even elements with 0.
public static void replaceEven(int[] arr)
{
for (int i = 0; i < arr.length; i++)
{
if (arr[i] % 2 == 0) // Number is even
{
arr[i] = 0;
}
}
}
public static void main(String[] args)
{
int[] randoms = new int[10];
// Create a test array containing random numbers.
for (int i = 0; i < 10; i++)
{
randoms[i] = (int) (Math.random() * 100) + 1;
// Print the values as they are assigned.
System.out.print(randoms[i] + " ");
}
System.out.println();
// Replace the even elements.
replaceEven(randoms);
// Print again to see new elements.
for (int i = 0; i < 10; i++)
{
System.out.print(randoms[i] + " ");
}
System.out.println();
}
d) Replace each element except first and last by the larger of its two neighbors.
public static void replaceWithLargestNeighbor(int[] arr)
{
// Start loop at one, and stop before the end
for (int i = 1; i < arr.length - 1; i++)
{
if (arr[i - 1] > arr[i + 1])
{
arr[i] = arr[i - 1];
}
else
{
arr[i] = arr[i + 1];
}
}
}
public static void main(String[] args)
{
int[] randoms = new int[10];
// Create a test array containing random numbers.
for (int i = 0; i < 10; i++)
{
randoms[i] = (int) (Math.random() * 100) + 1;
// Print the values as they are assigned.
System.out.print(randoms[i] + " ");
}
System.out.println();
// Replace with largest neighbor
replaceWithLargestNeighbor(randoms);
// Print again to see new elements.
for (int i = 0; i < 10; i++)
{
System.out.print(randoms[i] + " ");
}
System.out.println();
}
e) Remove the middle element if the array length is odd, or middle two if even.
public static void removeMiddle(int[] arr)
{
int size = arr.length;
if (size % 2 == 0) // Size is even
{
// Figure out starting point for removal
int firstToRemove = size / 2 - 1;
// Remove middle two elements
for (int i = firstToRemove; i < size - 2; i++)
{
arr[i] = arr[i + 2];
}
}
else // Size is odd
{
// Figure out starting point for removal
int firstToRemove = size / 2;
// Remove middle element
for (int i = firstToRemove; i < size - 1; i++)
{
arr[i] = arr[i + 1];
}
}
}
public static void main(String[] args)
{
int[] randoms = new int[11];
// Create a test array containing random numbers
for (int i = 0; i < randoms.length; i++)
{
randoms[i] = (int) (Math.random() * 100) + 1;
// Print the values as they are assigned.
System.out.print(randoms[i] + " " );
}
System.out.println();
// Remove the middle element(s)
removeMiddle(randoms);
// Print again to see new order.
for (int i = 0; i < randoms.length; i++)
{
System.out.print(randoms[i] + " ");
}
System.out.println();
randoms = new int[10];
// Create a test array with an even number of elements
for (int i = 0; i < randoms.length; i++)
{
randoms[i] = (int) (Math.random() * 100) + 1;
// Print the values as they are assigned.
System.out.print(randoms[i] + " " );
}
System.out.println();
// Remove the middle element(s)
removeMiddle(randoms);
// Print again to see new order.
for (int i = 0; i < randoms.length; i++)
{
System.out.print(randoms[i] + " ");
}
System.out.println();
}
f) Move all even elements to the front, otherwise preserving order
public static void moveEvenToFront(int[] arr)
{
int endOfEvens = 0;
int temp;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] % 2 == 0) // Even
{
temp = arr[i]; // Save the even number
// Move array element from end of
// evens to current location
for (int j = i; j > endOfEvens; j--)
{
arr[j] = arr[j - 1];
}
arr[endOfEvens] = temp;
endOfEvens++;
}
}
}
public static void main(String[] args)
{
int[] randoms = new int[10];
// Create a test array containing random numbers.
for (int i = 0; i < randoms.length; i++)
{
randoms[i] = (int) (Math.random() * 100) + 1;
// Print the values as they are assigned.
System.out.print(randoms[i] + " " );
}
System.out.println();
// Move the evens to the front.
moveEvenToFront(randoms);
// Print again to see new order.
for (int i = 0; i < randoms.length; i++)
{
System.out.print(randoms[i] + " " );
}
System.out.println();
}
g) Return second-largest element in array.
public static int getSecondLargest(int[] arr)
{
// One way to do it: Find maximum once.
int max = arr[0];
for (int i = 1; i < size; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
// 2. Find the max again, ignoring the real max.
int oldMax = max;
max = arr[0];
for (int i = 1; i < size; i++)
{
if (arr[i] != oldMax)
{
if (arr[i] > max)
{
max = arr[i];
}
}
}
return max;
}
public static void main(String[] args)
{
int[] randoms = new int[10];
// Create a test array containing random numbers.
for (int i = 0; i < randoms.length; i++)
{
randoms[i] = (int) (Math.random() * 100) + 1;
// Print the values as they are assigned.
System.out.print(randoms[i] + " " );
}
System.out.println();
// Find the second largest.
System.out.println("The second largest number is " +
+ getSecondLargest(randoms));
}
h) Return true if array is currently in increasing order.
public static boolean inOrder(int[] arr)
{
// Assume they are in order.
boolean ordered = true;
// Loop through array, checking for out
// of order elements
for (int i = 0; i < arr.length- 1; i++)
{
if (arr[i] > arr[i + 1])
{
ordered = false;
}
}
return ordered;
}
public static void main(String[] args)
{
int[] arrOrder= {1, 2, 3, 4, 5, 6, 7, 8, 9, 42};
int[] arrNotOrder = {2, 1, 3, 4, 5, 6, 7, 8, 9, 42};
// Check if array 1 is ordered or not.
if (inOrder(arrOrder))
{
System.out.println("The array is in order.");
}
else
{
System.out.println("The array is NOT in order.");
}
System.out.println("Expected: The array is in order.");
// Check if array 2 is ordered or not.
if (inOrder(arrNotOrder))
{
System.out.println("The array is in order.");
}
else
{
System.out.println("The array is NOT in order.");
}
System.out.println("Expected: The array is NOT in order.");
}
i) Return true if array contains two adjacent duplicate values.
public static boolean adjacentDupes(int[] arr)
{
// Assume no adjacent dupes.
boolean adjDupes = false;
// Loop through array, checking for duplicates
// next to each other.
for (int i = 0; i < arr.length- 1; i++)
{
if (arr[i] == arr[i + 1])
{
adjDupes = true;
}
}
return adjDupes;
}
public static void main(String[] args)
{
int[] arr1 = {1, 2, 3, 4, 4, 6, 7, 8, 9, 42};
int[] arr2 = {2, 1, 3, 4, 5, 4, 7, 4, 9, 4};
// Check if array 1 has adjacent dupes.
if (adjacentDupes(arr1))
{
System.out.println("Array contains adjacent duplicates.");
}
else
{
System.out.println("Array does NOT contain adjacent duplicates.");
}
System.out.println("Expected: Array contains adjacent duplicates.");
// Check if array 2 has adjacent dupes.
if (adjacentDupes(arr2))
{
System.out.println("Array contains adjacent duplicates.");
}
else
{
System.out.println("Array does NOT contain adjacent duplicates." );
}
System.out.println("Expected: Array does NOT contain adjacent duplicates.");
}
j) Returns true if array contains duplicate values (not necessarily adjacent).
public static boolean containsDuplicates(int[] arr)
{
// Assume no dupes.
boolean dupes = false;
// Loop through array, checking for duplicates
for (int i = 0; i < arr.length; i++)
{
for (int j = i + 1; j < arr.length; j++)
{
if (arr[i] == arr[j])
{
dupes = true;
}
}
}
return dupes;
}
public static void main(String[] args)
{
int[] arr1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 42};
int[] arr2 = {2, 1, 3, 4, 5, 4, 7, 4, 9, 4};
// Check if array 1 has dupes.
if (containsDuplicates(arr1))
{
System.out.println("Array contains duplicates.");
}
else
{
System.out.println("Array does NOT contain duplicates.");
}
System.out.println("Expected: Array does NOT contain duplicates.");
// Check if array 2 has dupes.
if (containsDuplicates(arr2))
{
System.out.println("Array contains duplicates.");
}
else
{
System.out.println("Array does NOT contain duplicates.");
}
System.out.println("Expected: Array contains duplicates.");
P6.3
import java.util.Scanner;
public class LargestAndSmallestInArray
{
public static void main(String[] args)
{
final int LENGTH = 100;
double[] data = new double[LENGTH];
int size = 0;
// Read inputs
System.out.println("Please enter values, Q to quit:");
Scanner in = new Scanner(System.in);
while (in.hasNextDouble() & size < data.length)
{
data[size] = in.nextDouble();
size++;
}
// Find the largest and smallest value
double largest = data[0];
double smallest = data[0];
for (int i = 1; i < size; i++)
{
if (data[i] > largest)
{
largest = data[i];
}
if (data[i] < smallest)
{
smallest = data[i];
}
}
// Print all values, marking the largest and smallest
for (int i = 0; i < size; i++)
{
System.out.print(data[i]);
if (data[i] == largest)
{
System.out.print(" <== largest value");
}
if (data[i] == smallest)
{
System.out.print(" <== smallest value");
}
System.out.println();
}
}
}
P6.4
import java.util.Scanner;
public class Scores
{
/**
Computes the sum of all values except the smallest in an array.
@param data an array of values
@return the sum of all but the leastvalue in data
*/
public static double sumWithoutSmallest(double[] data, int currentSize)
{
double total = 0;
double smallest = data[0];
for (int i = 0; i < currentSize; i++)
{
if (data[i] < smallest)
{
smallest = data[i];
}
total = total + data[i];
}
return total - smallest;
}
public static void main(String[] args)
{
final int LENGTH = 100;
double[] scores = new double[LENGTH];
int size = 0;
// Read inputs
System.out.println("Please enter scores, Q to quit:");
Scanner in = new Scanner(System.in);
while (in.hasNextDouble() & size < scores.length)
{
scores[size] = in.nextDouble();
size++;
}
if (scores.length == 0)
{
System.out.println("At least one score is required.");
return;
}
double total = sumWithoutSmallest(scores);
System.out.println("Final score without least one: " + total);
}
}
P6.5
public class RemoveMin
{
public static intremoveMin(double[] input, int currentSize)
{
// Find the minimum value first
double min = input[0];
int minPos = 0;
for (int i = 1; i < currentSize; i++)
{
if (input[i] < min)
{
min = input[i];
minPos = i;
}
}
// Now "eliminate" the minimum value
for (int j = minPos; j < currentSize - 1; j++)
{
input[j] = input[j + 1];
}
// Decrement the currentSize
currentSize--;
return currentSize;
}
public static void main(String[] args)
{
int[] myArray = new int[10];
int mySize = 0;
for (int i = 0; i < 6; i++)
{
myArray[i] = (int) (Math.random() * 100) +1;
mySize++;
}
for (int i = 0; i < mySize; i++)
{
System.out.print(myArray[i] + " ");
}
System.out.println();
removeMin(myArray, mySize);
for (int i = 0; i < mySize; i++)
{
System.out.print("myArray[i] + " ");
}
System.out.println();
}
}
P6.6
public class AlternatingSum
{
/**
Computes the alternating sum of the values in an array list
@param data an array list of values
@return the alternating sum of the values in data
*/
public static double alternatingSum(double[] data)
{
double total = 0;
for (int i = 0; i < data.length; i++)
{
if (i % 2 == 0)
{
total += data[i];
}
else
{
total -= data[i];
}
}
return total;
}
public static void main(String[] args)
{
double[] data = { 1, 4, 9, 16, 9, 7, 4, 9, 11 };
double total = alternatingSum(data);
System.out.println("Alternating sum: " + total);
}
}
P6.7
import java.util.Arrays;
public class ReverseElements
{
/**
Reverses an array.
@param data the input array
@return an array with the elements of data in reverse order
*/
public static double[] reverse(double[] data)
{
double[] revData = Arrays.copyOf(data, data.length);
int j = 0;
for (int i = data.length - 1; i >= 0; i--)
{
revData[j] = data[i];
j++;
}
return revData;
}
public static void main(String[] args)
{
double[] data = { 1, 4, 9, 16, 9, 7, 4, 9, 11 };
double[] reversed = reverse(data);
for (int i = 0; i < reversed.length; i++)
{
System.out.print(reversed[i] + " ");
}
System.out.println();
}
}
P6.8
public class Swap
{
public void swapHalves(int[] a)
{
int i = 0;
int j = a.length/ 2;
int temp;
while (i < a.length/ 2)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}
}
public static void main(String[] args)
{
int[] myArray= {1, 4, 9, 16, 9, 7, 4, 11};
swapHalves(myArray);
System.out.println("Printing the new array..." );
for (int i = 0; i < myArray.length; i++)
{
System.out.print("myArray[i] + " ");
}
System.out.println();
}
}
P6.9
public class BooleanEquals
{
public static boolean equals(int[] a, int[] b)
{
if (a.length!= b.length)
{
return false;
}
for (int i = 0; i < a.length; i++)
{
if (a[i] != b[i])
{
return false;
}
}
return true;
}
public static void main(String[] args)
{
int[] arr1= {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr2= {1, 2, 3, 4, 5, 6, 7, 8};
int[]arr3= {1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] arr4= {1, 2, 3, 4, 5, 4, 7, 8};
System.out.print("Arrays 1 and 2 are ");
if (!equals(arr1, arr2))
{
System.out.print("not ");
}
System.out.println("equal." );
System.out.print("Arrays 1 and 3 are ");
if (!equals(arr1, arr3))
{
System.out.print("not ");
}
System.out.println("equal." );
System.out.print("Arrays 1 and 4 are ");
if (!equals(arr1, arr4))
{
System.out.print("not ");
}
System.out.println("equal." );
}
}
P6.10
public class SetChecker
{
public static boolean isIn(int e, int[] b)
{
for (int i = 0; i < b.length; i++)
{
if (e == b[i])
{
return true;
}
}
return false;
}
public static boolean sameSet(int[] a, int[] b)
{
for (int i = 0; i < a.length; i++)
{
if (!isIn(a[i], b))
{
return false;
}
}
for (int i = 0; i < b.length; i++)
{
if (!isIn(b[i], a))
{
return false;
}
}
return true;
}
public static void main(String[] args)
{
int[] a= {1, 4, 9, 16, 9, 7, 4, 9, 11};
int[] b= {11, 11, 7, 9, 16, 4, 1};
System.out.print("The elements of the arrays a and b ");
if (!sameSet(a, b))
{
System.out.print("do not ");
}
System.out.println("form the same set." );
}
}
P6.11
public class Count
{
public static boolean count(int e, int[] b)
{
int count = 0;
for (int i = 0; i < b.length; i++)
{
if (e == b[i])
{
count++;
}
}
return count;
}
// This methodassumes that the two array arguments
// are the same size.
public static boolean sameElements(int[] a, int[] b)
{
for (int i = 0; i < a.length; i++)
{
if (count(a[i], a) != count(a[i], b))
{
return false;
}
}
return true;
}
public static void main(String[] args)
{
int[] a = {1, 4, 9, 16, 9, 7, 4, 9, 11};
int[] b= {11, 1, 4, 9, 16, 9, 7, 4, 9};
System.out.print("The arrays a and b ");
if (!sameElements(a, b))
{
System.out.print("do not ");
}
System.out.println("have the same elements." );
}
}
P6.12
public class PrintRun
{
/**
Makes an array with n random die (1-6) tosses
@param n the number of tosses to simulate
@return an array with n random die tosses in it
*/
public static int[] generateDieTosses(int n)
{
int[] tosses = new int[n];
for (int i = 0; i < n; i++)
{
tosses[i] = (int) (Math.random() * 6 + 1);
}
return tosses;
}
/**
Prints values in array by marking runs in parentheses.
@param values the input array to print
*/
public static void printRun(int[] values)
{
boolean inRun = false;
int previousValue = values[0];
for (int i = 0; i < values.length - 1; i++)
{
if (inRun)
{
if (values[i] != previousValue)
{
System.out.print(")");
inRun = false;
}
System.out.print(" ");
}
else
{
if (values[i] == values[i + 1])
{
System.out.print(" (");
inRun = true;
}
else
{
System.out.print(" ");
}
}
previousValue = values[i];
System.out.print(values[i]);
}
if (inRun & values[values.length - 1] == previousValue)
{
System.out.print(" " + values[values.length - 1] + ")");
}
else if (inRun & values[values.length - 1] != previousValue)
{
System.out.print(") " + values[values.length - 1]);
}
else
{
System.out.print(" " + values[values.length - 1]);
}
}
public static void main(String[] args)
{
int[] tosses = generateDieTosses(20);
printRun(tosses);
}
}
P6.13
public class PrintLongestRun
{
/**
Makes an array with n random die (1-6) tosses
@param n the number of tosses to simulate
@return an array with n random die tosses in it
*/
public static int[] generateDieTosses(int n)
{
int[] tosses = new int[n];
for (int i = 0; i < n; i++)
{
tosses[i] = (int) (Math.random() * 2 + 1);
}
return tosses;
}
/**
Print array with parentheses around element at index up to length long.
@param values the values to print
@param index the index to start parenthesis
@param length of the run of same values
*/
public static void printArrayWithParenthesis(int[] values, int index,
int length)
{
boolean inRun = false;
for (int i = 0; i < values.length; i++)
{
if (inRun)
{
if (length == 0)
{
System.out.print(") " + values[i] + " ");
inRun = false;
}
else
{
System.out.print(" " + values[i]);
}
length--;
}
else if (i == index)
{
inRun = true;
length--;
System.out.print("(" + values[i]);
}
else
{
System.out.print(values[i] + " ");
}
}
if (length == 0)
{
System.out.print(")");
}
}
/**
Prints values in array by marking runs in parentheses.
@param values the input array to print
*/
public static void printLongestRun(int[] values)
{
boolean inRun = false;
int previousValue = values[0];
int longestRunLength = 0;
int longestRunIndex = -1;
int currentRunLength = 0;
int currentRunIndex = -1;
for (int i = 0; i < values.length - 1; i++)
{
if (inRun)
{
if (values[i] != previousValue)
{
inRun = false;
if (currentRunLength > longestRunLength)
{
longestRunLength = currentRunLength;
longestRunIndex = currentRunIndex;
}
}
else
{
currentRunLength++;
}
}
else
{
if (values[i] == values[i + 1])
{
inRun = true;
currentRunLength = 1;
currentRunIndex = i;
}
}
previousValue = values[i];
}
if (inRun & values[values.length - 1] == previousValue)
{
currentRunLength++;
if (currentRunLength > longestRunLength)
{
longestRunLength = currentRunLength;
longestRunIndex = currentRunIndex;
}
}
printArrayWithParenthesis(values, longestRunIndex, longestRunLength);
}
public static void main(String[] args)
{
int[] tosses = generateDieTosses(20);
printLongestRun(tosses);
}
}
P6.14
import java.util.Arrays;
public class SortedSequence
{
/**
Makes an array with n random values between 0-99.
@param n the number of tosses to simulate
@return an array with n random die tosses in it
*/
public static int[] generateRandom(int n)
{
int[] tosses = new int[n];
for (int i = 0; i < n; i++)
{
tosses[i] = (int) (Math.random() * 100);
}
return tosses;
}
/**
Prints an array.
@param values the array to print
*/
public static void printArray(int[] values)
{
for (int i = 0; i < values.length; i++)
{
System.out.print(values[i] + " ");
}
System.out.println();
}
public static void main(String[] args)
{
int[] values = generateRandom(20);
printArray(values);
Arrays.sort(values);
printArray(values);
}
}
P6.15
public class GeneratePermutations
{
/**
Generates an array n elements long with numbers from 1 to n
@param n the length of the resulting array
@return an array with numbers 1 to n
*/
public static int[] generateArray(int n)
{
int[] list = new int[n];
for (int i = 0; i < n; i++)