Question

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 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++;
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Simple Mathematical Computations in Java
Homework Solution
$20.00
Java
Programming
Codes
Algorithms
Mathematics
Computer Science
Objects
Summation
Odd Digits
Even Digits
ItemIndex
Functions
Integers
Multiple Values
Statements
Variables
Input
Output
ChatBot Using Java Programming
Homework Solution
$7.00
Java
Programming
Coding
Chatting
Bot
Users
Computers
Sentences
Symbols
Instant Messaging
Input
Output
Special Characters
Even Numbers
Odd Numbers
Java Programming Assignment
Homework Solution
$30.00
Java Programming
Fibonacci NumbersIntegers
Computer Science
Pseudocode
Program
Code
Get help from a qualified tutor
Live Chats