USING JAVA WITH TIME COMPLEXITY OF O(N^2) OR LESS Harry was digging a hole to fi

Question

USING JAVA WITH TIME COMPLEXITY OF O(N^2) OR LESS

Harry was digging a hole to find hidden treasure in his grandmother’s backyard. There he discovered an old piece of paper with N integers written on it. From the game of numbers, Harry has learnt that a trio of numbers is special if and only if their sum is a mythical constant M.

Harry tries to find out how many distinct triplets of numbers, from the piece of paper, have their sum equal to M. Unfortunately, this problem is hard for him to crack and he needs your help.

Input:

Take input from a file in2.txt. The first line of the file contains the number of test cases T. The first line of each test case contains two integers N and M (separated by space), representing the number of integers in the sequence and the mythical constant respectively. Next line, contains N space separated integers (duplicate integers are allowed, negative numbers are allowed).

Output:

The output should contain only one integer, the number of distinct triplets which have their sum equal to M.

Sample Input:

1

10 5

1 10 4 3 2 5 0 1 9 5

Sample Output:

4

Expected Time Complexity:

No more than O(n2 )

Explanation:

There are 4 special trios for the above sample input: (0, 2, 6); (0, 3, 7); (2, 6, 7); (3, 4, 6) For the first trio (0, 2, 6): 1+4+0 = 5 For the second trio (0, 3, 7): 1+3+1 = 5 …

Note: Here we only show the positions (in input) of numbers in each trio.

Hint: Use hash table. You can implement your own hash table or use the built in one, either is fine

Explanation / Answer

import java.io.*;

import java.util.*;

public class triplets {

// returns all triplets whose sum is equal to sum value

public static List<List<Integer> > findTriplets(int[] nums, int sum)

{

/* Sort the elements */

Arrays.sort(nums);

List<List<Integer> > pair = new ArrayList<>();

TreeSet<String> set = new TreeSet<String>();

List<Integer> triplets = new ArrayList<>();

/* Iterate over the array from the start and

consider it as the first element*/

for (int i = 0; i < nums.length - 2; i++) {

// index of the first element in the

// remaining elements

int j = i + 1;

// index of the last element

int k = nums.length - 1;

while (j < k) {

if (nums[i] + nums[j] + nums[k] == sum) {

String str = nums[i] + ":" + nums[j] + ":" + nums[k];

if (true) {

// To check for the unique triplet

triplets.add(nums[i]);

triplets.add(nums[j]);

triplets.add(nums[k]);

pair.add(triplets);

triplets = new ArrayList<>();

set.add(str);

}

j++; // increment the second value index

k--; // decrement the third value index

} else if (nums[i] + nums[j] + nums[k] < sum)

j++;

else // nums[i] + nums[j] + nums[k] > sum

k--;

}

}

return pair;

}

public static void main(String[] args)

{   

ArrayList<String> temp=new ArrayList<String>();

try{

File file =new File("C:\Users\pe953157\Downloads\Ecliplse Project Files\Practice\src\test.txt");

Scanner sc = new Scanner(file);

while (sc.hasNextLine()){

temp.add(sc.nextLine());

}

}

catch(FileNotFoundException e){System.out.println("file is missing check once");}

String[] dummy=temp.get(1).split(" ");

String[] nums1 =temp.get(2).split(" ");

int nums[]=new int[nums1.length];

int k=0;

for(String i:nums1)

nums[k++]=Integer.parseInt(i);

int sum =Integer.parseInt(dummy[1]);

List<List<Integer> > triplets = findTriplets(nums, sum);

if (!triplets.isEmpty()) {

System.out.print(triplets.size()+" =");

System.out.println(triplets);

} else {

System.out.println("No triplets can be formed");

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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