top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Write a program that find all the pairs that add up to given number?

0 votes
583 views

Write a program which finds all pairs of elements in an array whose sum is equal to a given number

Input  array: [-2,1,3,5,6,7,8,10,12,15,17,19,20]
Sum : 20

Output

6, 12
3, 15
1, 17
-2, 20
8, 10

Required best time complexity and effective code

posted Sep 27, 2020 by Atindra Kumar Nath

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes
 
Best answer

The easiest way can be the below solution whose time complexity is O(n^2). Might not recommended for large arrays.

static void getPairsEasy(int[] ar, int sum) {
        for (int i = 0; i < ar.length; i++)
            for (int j = i + 1; j < ar.length; j++) {
                if (sum == ar[i] + ar[j])
                    System.out.println(ar[i] + "," + ar[j]);
            }
    }

The other solution could be below, whose time complexity is O(nLogn). Works only for sorted arrays.

    static void getPairsBinarySearch(int[] ar, int sum) { 
        Arrays.sort(ar);
        int i=0, j = ar.length - 1;
        while(i<j){
            if(sum==ar[i]+ar[j]){
                System.out.println(ar[i]+","+ar[j]);
                i++; j--;
            }else if(sum > ar[i]+ar[j]){
                i++;
            }else if(sum < ar[i]+ar[j]){
                j--;
            } 
        }
    }
answer Sep 28, 2020 by Tanay Hanuman Toor
Similar Questions
+1 vote

Say you are given

int a[ ] = {1,2,3,4};
int b[ ] = {4,3,2,1};
int S = 5;

Now the task is to find all pairs of two number which adds up to S (One number from a and other number from b).

+2 votes

Rohit wants to add the last digits of two given numbers.
For example, If the given numbers are 267 and 154, the output should be 11.

Below is the explanation -
Last digit of the 267 is 7
Last digit of the 154 is 4
Sum of 7 and 4 = 11

Write a program to help Rohit achieve this for any given two numbers.

Note: The sign of the input numbers should be ignored. i.e.
if the input numbers are 267 and 154, the sum of last two digits should be 11
if the input numbers are 267 and -154, the sum of last two digits should be 11
if the input numbers are -267 and 154, the sum of last two digits should be 11
if the input numbers are -267 and -154, the sum of last two digits should be 11

+2 votes

Given a set of random strings, write a function that returns a set that groups all the anagrams together.

Ex: star, dog, car, rats, arc - > {(star, rats), (arc,car), dog}

+2 votes

Input:
arr = {'a', 'b'}, length = 3

Output:
aaa
aab
aba
abb
baa
bab
bba
bbb

...