Question

The input consists of n numbers a1, a2, . . . , an and a target value t. The goal is to determine in how many possible ways can we add up two of these numbers to get t. Formally, your program needs to find the number of pairs of indices i, j, i < j such that ai+aj = t.

For example, for 2, 7, 3, 1, 5, 6 and t = 7, we can get t in two ways: 2+5 and 1 + 6. Note that some numbers may occur several times in the sequence. For example, if the sequence is 2, 7, 2, 3, 1, 5, 6 and t = 7, we can get t in three ways 2(first occurrence) + 5, 2(second occurrence) + 5, and 1 + 6.

Describe an O(n log n) algorithm for this problem, and implement it in Java or C++.

You must explain clearly why your algorithm runs in O(n log n) time. Input specification: The input consists of two lines. The first line contains two integers n and t, separated by space. The second line contains integers a1, a2, . . . , an, separated by spaces. You may assume that the integers, as well as the sum of two such numbers, fit in int. You may also assume that n is positive and not larger than 1,000,000. Output specification: the output contains a single line with the number of pairs that sum to t.

sample input:

6 7
2 7 3 1 5 6

sample output:

4

Answer 1

Code

import java.util.Scanner;
public class Main {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int size,t;
int arr[];
size=sc.nextInt();
t=sc.nextInt();
arr=new int[size];
for(int i=0;i<size;i++)
arr[i]=sc.nextInt();
  
int count=0;
  
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
if(arr[i]+arr[j]==t)
count++;
}
}
System.out.println("\n"+count);
}
  
}
output

If you have any query regarding the code please ask me in the comment i am here for help you. Please do not direct thumbs down just ask if you have any query. And if you like my work then please appreciates with up vote. Thank You.