Reference no: EM132245752
Question 1 - The greatest common divisor (gcd) of two positive integers is the largest integer that divides evenly into both of them.
Design a RECURSIVE algorithm to find the greatest common divisor of two positive integers p and q, using the property:
- If p > q, the gcd of p and q is the same as the gcd of q and p%q.
(Your solution must be recursive. Zero points will be given for solutions that do not use recursion.)
public static int gcd(int p, int q){
//...fill in this method...
}
Question 2 - Given a linked list comprised of nodes defined as below, and a pointer to the first node in the linked list (top), write a method (modifyList) to modify the given list in the following way. If the data in a given node is a positive number, insert data-1 copies of that node after the given node. If the data in a given node is zero or a negative number, remove that node from the list.
For example, if the initial list is
1 4 0 -3 2 -1
then the modified list would be
1 4 4 4 4 2 2
class Node {
public int data;
public Node next;
public Node(int d, Node n) {
data = d;
next = n;
}
}
void modifyList(Node top){
//...fill in this method...
}
Question 3 - Given an unordered array of integers that may contain duplicates, fill in the following method to remove duplicates, so that there is at most one element with any value.
Leave the first occurrence of an integer in the original order, and delete any later occurrences.
For example, given the array
2 8 4 8 9 4 8 5 4
the method would produce
2 8 4 9 5
public static void removeDuplicates(int[] x, int n){
//x is the array to be modified, n is the number of elements in the array
}