20 replies to this topic

[enigmas]

So ive been working on a piece of code that has 2 linked lists, and in these two linked lists are 2 huge numbers. The only other type that can hold these numbers is BigInt but I cant use it in my code. I want to do a mathematical operation on these 2 big numbers which are stored in the linked list but cant figure out how to do it. Anyone have any ideas?

[wim DC]

What do the linkedlists look like? Does each element contain a 1digit number (integer), or is it a char? or something else?
Number: 123456789123456789:
Integers
List: {1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9} OR List: {9,8,7,6,5,4,3,2,1,9,8,7,6,5,4,3,2,1}
OR
Character
List: {'1','2','3','4','5','6','7','8','9','1','2','3','4','5','6','7','8','9'} OR List: {'9','8','7','6','5','4','3','2','1','9','8','7','6','5','4','3','2','1'}
OR
Something else

[enigmas]

Each node in the linked list contains 1 integer. At first I stored the huge number in a list. Then I did 2 conversions to get it to an int. and then I put it in a for loop to input it into the list.

[wim DC]

I hope this example helps:

import java.util.LinkedList;


public class LinkList {


    LinkedList<Integer> list1;  //{1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9} [U][B]== 987654321987654321 -> numbers are stored in reverse![/B][/U]

    LinkedList<Integer> list2;  //{9,8,7,6,5,4,3,2,1,9,8,7,6,5,4,3,2,1} [U][B]== 123456789123456789 -> numbers are stored in reverse![/B][/U]

    

    public LinkList() {

        list1 = new LinkedList<Integer>();

        list2 = new LinkedList<Integer>();


        for (int i = 0; i < 2; i++) {

            for (int j = 1; j < 10; j++) {

                list1.add(j);

            }

            for (int j = 9; j > 0; j--) {

                list2.add(j);

            }

        }

    }



    /**

     * Add the number from list1 to list2.

     * @return a LinkedList containing the result.

     */

    public LinkedList<Integer> sum(){

        LinkedList<Integer> result = new LinkedList<Integer>();


        int extra=0;

        for(int i=0 ; i<list1.size() && i<list2.size() ; i++ ){

            int newNumber = list1.get(i) + list2.get(i);

            result.add((newNumber%10)+extra);

            extra = newNumber/10;  

        }


        if(list1.size()>list2.size()){

            for(int i=list2.size() ; i<list1.size() ; i++){

                result.add(list1.get(i));

            }

        } else if(list2.size()>list1.size()){

            for(int i=list1.size() ; i<list2.size() ; i++){

                result.add(list2.get(i));

            }

        }


        return result;

    }


    public static void main(String[] args){

        LinkList test = new LinkList();

        LinkedList<Integer> result = test.sum();

        for(int number : result){

            System.out.print(number);

        }

    }

}

[enigmas]

I meant to say at first they were stored in an intger but this should work as well. And did you just write this could by yourself? And so im assumng this code will add the two numbers together?

[wim DC]

enigmas said:

I meant to say at first they were stored in an intger but this should work as well. And did you just write this could by yourself? And so im assumng this code will add the two numbers together?

-So if Integer.maxValue = 2147483647, and you had a number that was 2147483648 then you would've stored it as
{2147483647, 1} ?

-Yes, I just wrote it.

-Yes, the code does 123456789123456789+987654321987654321 and prints the result (in reverse because i forgot it was reverse and should loop trough the result the other way :P)

[enigmas]

...wow i screwed up agian... It was stored in a STRING. sorry about that im swamped with work and I cant think straight anymore.
String first = ("93840412348320948230948982306");

Then i stored each digit as an int in my linked list, each node would hold exactly 1 digit.

[wim DC]

Well that's just my code then, exccept that you first need to do Integer.parseInt(digit)
Or an alternative way isntead of parsing is get a char out of the digit , cast to integer and do -48.

char k = '1';

int number = ((int) k) -48;

or if 1 is in a string:

String k ="1";

int number= ((int) k.charAt(0))-48;

It could be possible that this is faster than the parsing if you look at microseconds :D.. but no idea really.


edit: It's not int.parse, but Integer.parseInt

[enigmas]

I already parsed it and put it in the linked list. My problem is figuring out how to add the two large numbers together in the 2 linked lists. I dont want to combine the numbers but what I want is to add 93840412348320948230948982306 and 30330924824982438024988. Each of these numbers are stored in the linked list, one digit in each node.

[wim DC]

And this is not working?

public LinkedList<Integer> sum(){

        LinkedList<Integer> result = new LinkedList<Integer>();


        int extra=0;

        for(int i=0 ; i<list1.size() && i<list2.size() ; i++ ){

            int newNumber = list1.get(i) + list2.get(i);

            result.add((newNumber%10)+extra);

            extra = newNumber/10;  

        }


        if(list1.size()>list2.size()){

            for(int i=list2.size() ; i<list1.size() ; i++){

                result.add(list1.get(i));

            }

        } else if(list2.size()>list1.size()){

            for(int i=list1.size() ; i<list2.size() ; i++){

                result.add(list2.get(i));

            }

        }


        return result;

    }

Okay this requires the numbers ot be in the linkedlist in reverse, but you can change the code around so that isn't required.
The biggest change would be that isntead of
list1.get(i);
you would need
list1.get(list1.size() - i -1);
Ditto for every other get.

[enigmas]

Alright thank you very much, I will try the code laster tonight or early tomorrow and ill get back to you. Thanks again for all your help its greatly appreciated

[enigmas]

So I am still not amazing at programming and I have trouble using code that isnt mine. I am doing my best to decipher to code you have provided for me. You named your method public LinkedList<Integer> sum(); Couldnt I just call it public sum();

This is the code I have so far if it would help. I am only showing the class for inputing to the linked list and calling the class. If you would like I can also provide my linkedlist class.

import java.math.BigInteger;

import java.util.*;


public class GCD {

	//Main method

	int i=0;

	char x;

	char c;

	public static void main(String[] args)

	{

		//GCD tester =new GCD();

		String first = ("93840412348320948230948982306");

		String second = ("30330924824982438024988");

		new GCD(first,second);

		//System.out.println ("Hello Friend");


 

    

	}


	public GCD (String j,String k)

	{

		//System.out.println("We are in GCD constructor");

		linkedlist lList1 =new linkedlist();

		linkedlist lList2 =new linkedlist();

		for (i=0;i<j.length();i++)

		{	

			//System.out.println ("We are in first for loop");

			x = j.charAt(i);

			String tempString = Character.toString(x);

			int tempInt = Integer.parseInt (tempString);

			lList1.addtoendr(tempInt);

			System.out.println(lList1.getitemr(i+1));

		}	

		for (i=0;i<k.length();i++)

		{

			//System.out.println("We are in second for loop");

			c=k.charAt(i);

			String tempString1 = Character.toString(c);

			int tempInt1 = Integer.parseInt(tempString1);

			lList2.addtoendr(tempInt1);

			System.out.println (lList2.getitemr(i+1));

		}

	}

}