Given a non-sorted array A of n integers and an integer value x: a) Similar to Q

Question

Given a non-sorted array A of n integers and an integer value x: 

a) Similar to Question 1(shown below *), develop well-documented pseudo code that finds all pairs of elements of the array that subtract to exactly to |x|. The code however must be different than the one you had in Question 1 and must use either a stack S or a queue Q to perform what is needed. 

b) Briefly justify the motive(s) behind your design.

c) What is the Big-O complexity of your solution? Explain clearly how you obtained such complexity. 

d) What is the Big- complexity of your solution? Explain clearly how you obtained such complexity.

e) What is the Big-O space complexity of the utilized stack or queue? Explain your answer.

*Develop well-documented pseudo code that finds all the two elements of a given array that subtract exactly to |x| (absolute value of x). The code must display the indices and the values of these elements. For instance, given the following array (13, 1,-8, 21, 0, 9,-54, 17, 31, 81,-46) and x as 8, your code should find and display something similar to the following (notice that this is just an example. Your solution must not refer to this particular example): All pairs of elements of the array that subtract exactly to absolute value of 8 are: Indices 0 & 3 with values 13 & 21 (e.g., 13-21= | 8 |) Indices 1 & 5 with values 1 & 9 Indices 2 & 4 with values -8 & 0 Indices 6 & 10 with values -54 & -46 Etc. 

Explanation / Answer

import java.util.*;
public class MyClass {
public static void main(String args[]) {
int[] arr={13, 1,-8, 21, 0, 9,-54, 17, 31, 81,-46};
int k=8;
int size=arr.length;
HashMap<Integer,Integer> resultMap=new HashMap<Integer,Integer>();

for (int i = 0; i < size; i ++)
resultMap.put(arr[i], 0);

System.out.println("All found pairs of indices for given value " + k);   

for (int j = 0; j < size; j ++){
if (resultMap.containsKey(k - arr[j]) && resultMap.get(k - arr[j])!=1 ){ //check if the map contains key and
resultMap.put(k - arr[j], 1); // its not repeated
System.out.println(arr[j]+ " " + (k- arr[j]) );
}
if (resultMap.containsKey(k + arr[j]) && resultMap.get(k + arr[j])!=1){
resultMap.put(k + arr[j], 1);
System.out.println(arr[j]+ " " + (k+ arr[j]) );  
  
}  
}   
  
}
}

Complexity is O(N) , as there two seperated for loop and each of them having constant operation inside the loop.

Big-O space is O(N) , as to store the array in Hashmap

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.