Write a program called Target in Java that reads in a text file, in.txt, that contains a list of positive integers, duplicates are possible, separated by spaces. Zero is not included. After reading the integers, the program saves them in a singly linked list in the same order in which they appear in the input file. Then, without changing the linked list, the program should print whether there exists a partition of the list (two subsets whose union contains all the elements and intersection contains none of the elements) whose sums have a greatest common divisor, GCD, of another target value. Assume that in.txt is in the
same folder as your Java files and that it contains at least one integer. The following are examples of possible input. You do not need to output anything but a YES or NO.
{1, 2, 3} with target GCD 2 should output YES because the sum of the set {1, 3} and sum of the set {2} have a GCD of 2.
{3, 3, 5, 7} with a target GCD 3 should output YES because the sum of the set {3, 5, 7} and sum of the set {3} have a GCD of 3.
{32, 45, 73} with a target GCD 15 should output YES because the sum of the set {32, 73} and sum of the set {45} have a GCD 15.
{70, 73, 50, 77, 38} with a target GCD 44 should output YES because the sum of the set {70, 73, 77} and the sum of the set {50, 38} have a GCD of 44.
{70, 73, 50, 77, 38} with a target GCD 7 should output YES because the sum of the set {70, 77} and sum of the set {73, 50, 38} have a GCD of 7.
Breakdown of the last example. The sum of 70 and 77 is 147 and the sum of 73 and 50 and 38 is 161. The GCD of 147 and 161 is 7, which is the target GCD.
Note that a set can have many partitions that give a YES. For instance,
{71, 84, 97, 24, 8} with a target GCD of 4 has the following partitions that work.
{71, 97} and {84, 24, 8}
{71, 84, 97, 24} and {8}
{71, 97, 24} and {84, 8}
{71, 84, 97, 8} and {24}
{71, 84, 97} and {24, 8}
{71, 97, 8} and {84, 24}
{71, 97, 24, 8} and {84}
All your program should output is a YES or a NO. Here are some examples of NO partitions and targets.
{100, 33, 60} with a target GCD 3 should output NO.
{74, 93, 58, 29, 47, 37, 21, 77, 38, 1} with target GCD 23 should output NO.
{3, 3, 1, 8, 7} with a target GCD 3 should output NO.
At the end of this document, I have given you a method that will return the GCD of two numbers so you only need to focus on partitioning the list and checking against a target value.
Your program must:
1.) Implement a linked list. You are required to implement a linked list from scratch without using any other Java libraries. For example, you are not allowed to use any built-in dynamic data structures, such as ArrayList or LinkedList. There is no need to provide a full-fledged implementation of a linked list. Keep your linked list implementation minimal and implement as much as you need to solve the problem. Each node of the linked list must include only two elements: an integer and a reference to the next element from the list.
2.) Read the integers from the file in.txt and store them into the linked list in the same order in which they appear in the input file. No calculations are allowed at this step, the program must only read the input numbers and store them into the linked list.
3.) Work on the linked list to find out if there exists a partition in which both subset sums have a greatest common divisor equal to some target value. The target value is not part of the in.txt file. No additional data structures are allowed. All computations must be done in place on the original data structure. In other words, your program can use only one data structure (and only one instance of it), the linked list, some auxiliary scalar variables and reference variables (used to point to different nodes of the list), and the gcd method I will give you. For the gcd method you will need to import BigInteger but you may NOT use BigInteger anywhere else in your program. No additional data structures are allowed, such as a second linked list, an array, string, etc. The only exception is I/O where you can use strings to read in.txt. You can use standard I/O libraries to perform I/O. For example, you can use StringTokenizer or Scanner. This is the only place you can use strings and libraries. If you have any questions about whether you can use a certain construct, email me.
4.) Prints YES or NO if a partition can be found that fits the criteria.
5.) Your program should not modify the linked list, i.e., it should remain in its original form as it was read from the input file in.txt.
HW2 must be solved by working on the linked list. For example, bypassing the homework restrictions by saving the numbers in a string, array, or any other data structure (except for the linked list) is not allowed and will be penalized. There must be only one instance of the list and it must not be changed after you have read the numbers from in.txt. In other words, you may not manipulate the list such as sorting, shuffling, or any other such manipulations. Using an integer as a binary mask to store information about subset membership is not a solution because a fixed-length binary mask cannot handle lists of arbitrary length. You will be penalized for using a solution such as this.
Place all your code into one class file (one .java file). Inner classes are allowed. Try to write simple and short programs. I/O, exception handling, and the linked list implementation should be kept to a minimum. You can also assume that input is correct and that in.txt is in the same folder as your Java program.
private static int gcd(int num1, int num2) {
BigInteger bigNum1 = new BigInteger(String.valueOf(num1));
BigInteger bigNum2 = new BigInteger(String.valueOf(num2));
return bigNum1.gcd(bigNum2).intValue();
}
Contact us for this Java assignment Solutions by Codersarts Specialist who can help you mentor and guide for such Java programming assignments.
We also provide help in Java assignment , homework, Coursework, final year mini - project, major project and development work help.
contact us now at contact@codersarts.com and get in touch with our team of Java experts
Comments