# Intersections & Unions

• (3 Pages)
• 1
• 2
• 3

## 30 Replies - 17397 Views - Last Post: 01 April 2011 - 08:33 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=225078&amp;s=ddef2096486327f17bae0910c1995167&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 KeithStone

Reputation: 1
• Posts: 50
• Joined: 29-March 11

# Intersections & Unions

Posted 29 March 2011 - 09:02 PM

I need to write a program that outputs the intersection and union of 2 set inputs, up to 500 numbers. Here's where I'm running into an issue, I can't use any set classes.

So, for example:

Input:
1 3 5 7 9
2 4 6 8

Output:
Intersection:
Union: 1 2 3 4 5 6 7 8 9

Example #2

Input:
1 3 5
1 3 8

Output:
Intersection: 1 3
Union: 1 3 5 8

I'm confused at where to start and I know you guys frown on that, but can someone give me a hand at where to start?

Is This A Good Question/Topic? 0

## Replies To: Intersections & Unions

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12274
• Posts: 45,364
• Joined: 27-December 08

## Re: Intersections & Unions

Posted 29 March 2011 - 09:14 PM

Take a look at using Sets here. Intersection is pretty easy, since the Set interface has an addAll() method. Unions are a little different. Take the smaller of the two Sets. For each element in the first Set that is in the second, add it to a third result Set.

### #3 KeithStone

Reputation: 1
• Posts: 50
• Joined: 29-March 11

## Re: Intersections & Unions

Posted 29 March 2011 - 09:26 PM

KeithStone, on 29 March 2011 - 09:02 PM, said:

I can't use any set classes.

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12274
• Posts: 45,364
• Joined: 27-December 08

## Re: Intersections & Unions

Posted 29 March 2011 - 09:29 PM

Sorry, I missed that.

You can still do that with ArrayList. Same concept, and basically the same methods.

### #5 KeithStone

Reputation: 1
• Posts: 50
• Joined: 29-March 11

## Re: Intersections & Unions

Posted 30 March 2011 - 06:02 PM

I have made it this far:

```import java.util.Scanner;

public class Test
{
public static void main (String[] args)
{

Scanner scan = new Scanner( System.in );
int[] array1 = new int[100];
int[] array2 = new int [100];

for( int i = 0; i < array1.length; i++ )
{
System.out.println("First set ending in -1");
array1[i] = scan.nextInt( );
for( int j = 0; j < array2.length; j++ )
{
System.out.println("Second set ending in -1");
array2[j] = scan.nextInt();

if( array1[i] == array2[j] )
System.out.println("Intersection at: " + array1[i] );
if(array1[i] != array2[j])
System.out.println("Intersection at: ");
}
}
}
}

```

My output isn't correct though.
Example input: 1 3 5 7 9 gives me:
Second set ending in -1
Intersection at:
Second set ending in -1
Intersection at:
Second set ending in -1
Intersection at:
Second set ending in -1
Intersection at:
Second set ending in -1

But, if I only enter one number, say 5 for both, I get:
First set ending in -1
5
Second set ending in -1
5
Intersection at: 5
Second set ending in -1

Can you help me understand what I'm doing incorrectly?

### #6 KeithStone

Reputation: 1
• Posts: 50
• Joined: 29-March 11

## Re: Intersections & Unions

Posted 30 March 2011 - 06:08 PM

Quote

I had originally screwed up and used [\code] but edited the post.

This post has been edited by KeithStone: 30 March 2011 - 06:08 PM

### #7 KeithStone

Reputation: 1
• Posts: 50
• Joined: 29-March 11

## Re: Intersections & Unions

Posted 30 March 2011 - 08:39 PM

Can anyone help me out with this?

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12274
• Posts: 45,364
• Joined: 27-December 08

## Re: Intersections & Unions

Posted 30 March 2011 - 08:52 PM

You posted your code only a few hours ago. Seriously, be patient. Most questions are answered within 48 hours, and usually less than that.

Check your input loop. Your loop for getting the second set input is within the loop for getting the input for the first set.

Also, using an ArrayList over an array will make your life a lot easier. It's a List, not a Set, so you should be good in terms of staying within the guidelines. Methods like retainAll() make intersections so easy to detect. And the add() method makes unions a lot easier as well, since you can modify the List structure.

### #9 KeithStone

Reputation: 1
• Posts: 50
• Joined: 29-March 11

## Re: Intersections & Unions

Posted 30 March 2011 - 09:23 PM

I'm not following you - how do I use a an ArrayList with scanner?
Do you have an example of some code that I can look at?

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12274
• Posts: 45,364
• Joined: 27-December 08

## Re: Intersections & Unions

Posted 30 March 2011 - 09:26 PM

Locke has a tutorial on ArrayLists vs. Static Arrays that you might find helpful. Also check out the documentation.

### #11 KeithStone

Reputation: 1
• Posts: 50
• Joined: 29-March 11

## Re: Intersections & Unions

Posted 30 March 2011 - 10:24 PM

I came up with this, but I don't think I'm on the right track.

```
import java.util.*;
public class Test2{
public static void main(String[]args){
List a = new ArrayList();
Scanner input=new Scanner(System.in);
System.out.println("Enter first set: ");
for(int i=0;i < 5;i++){
String st=input.next();
}
List b = new ArrayList();
System.out.println("Enter second set: ");
for(int i=0;i < 5;i++){
String st=input.next();
}
}

```

### #12 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12274
• Posts: 45,364
• Joined: 27-December 08

## Re: Intersections & Unions

Posted 31 March 2011 - 04:11 AM

Java Collections are generic. So you should be storing a List<Integer> or List<String> if you want your ArrayList to be storing Integers or Strings respectively. You should not be storing just a plain List.

You're on the right track, though.

### #13 cfoley

• Cabbage

Reputation: 2388
• Posts: 5,013
• Joined: 11-December 07

## Re: Intersections & Unions

Posted 31 March 2011 - 04:41 AM

Dude, he needs help on writing an algorithm, not a lesson on data structures.

Union

Basically you want to join the two sets together but make sure you don't have any duplicates. Here's an easy description of how to do it:

1. Create a new set for the union.
2. Add all of the first set to it.
3. Take each item in the second set in turn.
4. Check to see if it is in the first set.
5. Add it to the union set if it is not in the first set.

Intersection

Here you are looking for items that appear in both sets.

1. Create an intersection set.
2. Take each item in the first set in turn.
3. Check to see if it is in the second set.
4. Add it to the intersection if it is in the second set.

Step 4 for the union and step 3 in the intersection are the same and will require a few lines of code. I suggest combining them into a method that returns a boolean.

Have a shot at coding these and we can look at your code then.

Since you're finding this difficult, choose whatever data structure you are most comfortable with. Arrays, ArrayLists, Vectors, LinkedLists and Queues are all fine. You can do this with any of them.

I also suggest that to begin with you hard code a couple of sets. You are almost there with your user entry... but that is the icing on the cake. Get the important stuff done first.

This post has been edited by cfoley: 31 March 2011 - 04:42 AM

### #14 KeithStone

Reputation: 1
• Posts: 50
• Joined: 29-March 11

## Re: Intersections & Unions

Posted 31 March 2011 - 09:07 PM

Can someone just explain to me how I can get the loop to turn off in this code? I'm not wrapping my head around this.
```
import java.util.Scanner;

public class Test
{
public static void main (String[] args)
{

Scanner scan = new Scanner( System.in );
int[] array1 = new int[100];
int[] array2 = new int [100];

for( int i = 0; i < array1.length; i++ )
{
System.out.println("First set ending in -1");
array1[i] = scan.nextInt( );
for( int j = 0; j < array2.length; j++ )
{
System.out.println("Second set ending in -1");
array2[j] = scan.nextInt();

if( array1[i] == array2[j] )
System.out.println("Intersection at: " + array1[i] );
if(array1[i] != array2[j])
System.out.println("Intersection at: ");
}
}
}
}

```

### #15 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12274
• Posts: 45,364
• Joined: 27-December 08

## Re: Intersections & Unions

Posted 31 March 2011 - 09:13 PM

You want to check for unions and intersections after you populate your arrays. You shouldn't need nested loops initially to populate your arrays. Here's the logic you want to incorporate:
```for(int i = 0; i < myArr.length; i++){
//get input
//if the input is -1, break
//otherwise, assign it to myArr[i]
}
for(int i = 0; i < myArr2.length; i++){
//same process for getting input and
//assigning it to myArr2's elements
}

//Now that we have user input
//let's look at performing our
//union and intersection

```

Quote

Dude, he needs help on writing an algorithm, not a lesson on data structures.

It's just easier to do this with ArrayLists because of the built in functionality.