Question

/*
*

  
  
Suppose we want to implement a class IntArraySet.
The difference of this class from IntArrayBag is that each item can only occur once in the set
We will use the same instance variables.

*/

public class IntArraySet
{
private int[ ] data;
private int manyItems;


public IntArraySet()
{
this(10);
}

public IntArraySet(int initialCapacity)
{
if (initialCapacity < 0)
throw new IllegalArgumentException
("The initialCapacity is negative: " + initialCapacity);
data = new int[initialCapacity];
manyItems = 0;
}

public int size() {return manyItems;}
  
public void ensureCapacity(int minimumCapacity)
{
int[ ] biggerArray;

if (data.length < minimumCapacity)
{
biggerArray = new int[minimumCapacity];
System.arraycopy(data, 0, biggerArray, 0, manyItems);
data = biggerArray;
}
}

//2. (7 points) complete add method: if it is not in the set yet, add it, and return true;
// otherwise, return false
// Don't use any method not defined in the class IntArraySet.   
public boolean add(int element)
{
  
  
  
}
// 3. (2 points) What is the complexity of the add method in the worst case?
//
  
}

Answer 1

If you have any problem with the code feel free to comment.

add method

//copy the rest of the code here    
public boolean add(int element) {
                
                //checking if any duplicate element is present or not
                for(int i=0; i<manyItems; i++) {
                        if(data[i] == element)
                                return false;
                }
                
                //adding the element to array
                for(int i=0; i<manyItems; i++) {
                        if(data[i] == 0) {
                                data[i] = element;
                                return true;
                        }
                }
                
                return false;
        }

Complexity

The complexity of the add method is big O(n) as in the worst case the duplicate element may be present in the last index of the array and will result in a false output. Same goes for adding the element to the array.