Question

In java What program would you write to solve the following problems and why does it work? Please also comment on other students’ code at least three times. 1) Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x. The partition element x can appear anywhere in the “right partition”; it does not need to appear between the left and right partitions. Input: 3à5à8à5à10à2à1 (partition=5) Output: 3à1à2à10à5à5à8. 2) Write a method that finds the maximum of two numbers. You should not use if-else or any other comparison operator. 3) Write methods to implement the multiply, subtract and divide operations for integers. The results of all of these are integers. Use only the add operator.

Answer 1

1) Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x. The partition element x can appear anywhere in the “right partition”; it does not need to appear between the left and right partitions.

Code:

public class Main {
static class Node
{
int data;
Node next;
}
static Node newNode(int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
return new_node;
}
static Node partition(Node head, int x)
{
Node tail = head;
Node curr = head;
while (curr != null)
{
Node next = curr.next;
if (curr.data < x)
{
curr.next = head;
head = curr;
}
  
else
{
tail.next = curr;
tail = curr;
}
curr = next;
}
tail.next = null;
return head;
}
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
public static void main(String[] args)
{
Node head = newNode(3);
head.next = newNode(5);
head.next.next = newNode(8);
head.next.next.next = newNode(5);
head.next.next.next.next = newNode(10);
head.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next = newNode(1);
  
int x = 5;
head = partition(head, x);
printList(head);
}
}

2) Write a method that finds the maximum of two numbers. You should not use if-else or any other comparison operator.

class Main
{
static int largestNum(int a, int b)
{
return a * ((a / b) > 0 ? 1 : 0) + b * ((b / a) > 0 ? 1 : 0);
}
public static void main(String[] args)
{
int a = 456, b = 568;
System.out.print(largestNum(a, b));
}
}

3) Write methods to implement the multiply, subtract and divide operations for integers. The results of all of these are integers. Use only the add operator

class Main{
static int flipSign(int a)
{
int neg = 0;
int tmp = a < 0 ? 1 : -1;
while (a != 0)
{
neg += tmp;
a += tmp;
}
return neg;
}
static boolean areDifferentSign(int a, int b)
{
return ((a < 0 && b > 0) || (a > 0 && b < 0));
}
static int sub(int a, int b)
{
return a + flipSign(b);
}
static int mul(int a, int b)
{   
if (a < b)
return mul(b, a);
int sum = 0;
for (int i = Math.abs(b); i > 0; i--)
sum += a;
if (b < 0)
sum = flipSign(sum);
  
return sum;
}
static int division(int a, int b)
{
if (b == 0)
throw new ArithmeticException();
int quotient = 0, dividend;
int divisor = flipSign(Math.abs(b));
for (dividend = Math.abs(a); dividend >= Math.abs(divisor);
dividend += divisor)
quotient++;
if (areDifferentSign(a, b))
quotient = flipSign(quotient);
return quotient;
}
public static void main(String[] args)
{
System.out.println("Subtraction : " + sub(6, 1));
System.out.println("Multiplication : " + mul(7, 6));
  
try
{
System.out.println("Division : " + division(8, 4));
}
  
catch (ArithmeticException e)
{
System.out.println("Exception :- Divide by 0");
}
}
}