QuestionQuestion

Write a program in Java that reads a text file, which contains a list of positive and negative integers separated by spaces and/or line breaks. Zero cannot be included. The program will save the integers in a single linked list in the same order they appear in the text file. Without changing the linked list, the program prints out the size of the largest zero sum subset of integers. If the list does not contain a subset of integers whose sum is zero, then the program will print out zero. The text file will be in the same folder as the java files.

The program has to do the following:
1. Implement the linked list without using any language libraries or any built-in dynamic data structures. Keep the linked list implementation minimal and implement enough needed to solve the problem. Each node of the linked list must include two elements, an integer and a reference to the next element from the list.
2. Read the integers from the text file. No calculations are allowed at this step. The program only reads the input numbers and stores them into the linked list.
3. Work on the linked list to find out the size of the largest zero-sum subset. No additional data structures are allowed. All computations are completed in place on the original data structure, which is the linked list. Some auxiliary scalar variables and reference variables can be used to point to different nodes on the list. Do not use an array or strings. The only exception is I/O libraries to perform I/O, for example StringTokenizer or scanner.
4. Print the size of the largest zero sum subset.
5. Do not modify the linked list, it should remain in its original form as it was read from the input file.

Additional notes:
- Using an integer as a binary mask to store data about subset membership is not allowed. A fixed length binary mask is not able to handle lists of arbitrary length.
- Provide a brief explanation of how the algorithm works using pseudo-code.

Zero sum subset examples:
The text file contains 4 -2 6, the program should print out 0. There is not a subset of integers where the sum is 0.
The text file contains 4 -1 3 1 -4. The zero sum subsets are (4, -4); (-1, 1); (4, 1, -4, -1). The largest zero sum subset is (4, 1, -4, -1) and the size is 4.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public class ZeroSumLinkedList {

class Node{
int data;
Node next;
}

int size;
Node head;

public ZeroSumLinkedList()
{
head = null;
size = 0;
}

public void add(int data)
{
Node node = new Node();
node.data = data;
node.next = null;
if(head == null)
{
head = node;
}
else
{
Node temp = head;
for(int i = 0; i < size-1; i++)
temp = temp.next;
temp.next = node;
}
size++;
}...
$40.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats