Given a linked list, and a number, check if their exist two numbers whose sum is equal to given number. If there exist two numbers, print them. If there are multiple answer, print any of them.
Examples:
Input : 1 -> 2 -> 3 -> 4 -> 5 -> NULL
sum = 3
Output : Pair is (1, 2)
Input : 10 -> 12 -> 31 -> 42 -> 53 -> NULL
sum = 15
Output : NO PAIR EXIST
Method(Brute force): Iteratively check if their exist any pair or not
Implementation:
C++
// CPP code to find the pair with given sum#include <bits/stdc++.h>using namespace std;/* Link list node */struct Node { int data; struct Node* next;};/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */void push(struct Node** head_ref, int new_data){ /* allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node;}/* Takes head pointer of the linked list and sum*/int check_pair_sum(struct Node* head, int sum){ struct Node* p = head, *q; while (p != NULL) { q = p->next; while (q != NULL) { // check if both sum is equal to // given sum if ((p->data) + (q->data) == sum) { cout << p->data << " " << q->data; return true; } q = q->next; } p = p->next; } return 0;}/* Driver program to test above function */int main(){ /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct linked list*/ push(&head, 1); push(&head, 4); push(&head, 1); push(&head, 12); push(&head, 1); push(&head, 18); push(&head, 47); push(&head, 16); push(&head, 12); push(&head, 14); /* function to print the result*/ bool res = check_pair_sum(head, 26); if (res == false) cout << "NO PAIR EXIST"; return 0;} |
Java
// Java code to find the pair with given sumimport java.util.*;class GFG { /* Link list node */ static class Node { int data; Node next; }; static Node head; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ // Inserting node at the beginning static Node push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head = head_ref; } /* Takes head pointer of the linked list and sum*/ static boolean check_pair_sum(Node head, int sum) { Node p = head, q; while (p != null) { q = p.next; while (q != null) { // check if both sum is equal to // given sum if ((p.data) + (q.data) == sum) { System.out.print(p.data + " " + q.data); return true; } q = q.next; } p = p.next; } return false; } // Driver Code public static void main(String[] args) { /* Start with the empty list */ head = null; /* Use push() to construct linked list*/ push(head, 1); push(head, 4); push(head, 1); push(head, 12); push(head, 1); push(head, 18); push(head, 47); push(head, 16); push(head, 12); push(head, 14); /* function to print the result*/ boolean res = check_pair_sum(head, 26); if (res == false) System.out.print("NO PAIR EXIST"); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for finding the pair with given sumimport mathimport sys# Link list node #class Node: def __init__(self, data): self.data = data self.next = None# Given a reference (pointer to pointer) to the head# of a list and an int, push a new node on the front# of the list.def push(head, data): if head == None: return Node(data) # allocate node temp = Node(data) # link the old list of the new node temp.next = head # move the head to point to the new node head = temp return head# Takes head pointer of the linked list and sumdef check_pair_sum(head, _sum_): p = head q = None while(p): q = p.next while(q): if p.data+q.data == _sum_: print("{} {}".format(p.data, q.data)) return True q = q.next p = p.next return False# Driver program to test above functionif __name__ == '__main__': # Start with the empty list head = None # Use push() to construct linked list head = push(head, 1) head = push(head, 4) head = push(head, 1) head = push(head, 12) head = push(head, 1) head = push(head, 18) head = push(head, 47) head = push(head, 16) head = push(head, 12) head = push(head, 14) # function to print the result res = check_pair_sum(head, 26) if (res == False): print("NO PAIR EXIST")# This code is contributed by Vikash Kumar 37 |
C#
// C# code to find the pair with given sumusing System;class GFG { /* Link list node */ public class Node { public int data; public Node next; }; static Node head; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ // Inserting node at the beginning static Node push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head = head_ref; } /* Takes head pointer of the linked list and sum*/ static Boolean check_pair_sum(Node head, int sum) { Node p = head, q; while (p != null) { q = p.next; while (q != null) { // check if both sum is equal to // given sum if ((p.data) + (q.data) == sum) { Console.Write(p.data + " " + q.data); return true; } q = q.next; } p = p.next; } return false; } // Driver Code public static void Main(String[] args) { /* Start with the empty list */ head = null; /* Use push() to construct linked list*/ push(head, 1); push(head, 4); push(head, 1); push(head, 12); push(head, 1); push(head, 18); push(head, 47); push(head, 16); push(head, 12); push(head, 14); /* function to print the result*/ Boolean res = check_pair_sum(head, 26); if (res == false) Console.Write("NO PAIR EXIST"); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript code to find the pair with given sum/* Link list node */class Node { constructor() { this.data = 0; this.next = null; }};var head = null;/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */// Inserting node at the beginningfunction push(head_ref, new_data){ /* allocate node */ var new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head = head_ref;}/* Takes head pointer of the linked list and sum*/function check_pair_sum(head, sum){ var p = head, q; while (p != null) { q = p.next; while (q != null) { // check if both sum is equal to // given sum if ((p.data) + (q.data) == sum) { document.write(p.data + " " + q.data); return true; } q = q.next; } p = p.next; } return false;}// Driver Code/* Start with the empty list */head = null;/* Use push() to construct linked list*/push(head, 1);push(head, 4);push(head, 1);push(head, 12);push(head, 1);push(head, 18);push(head, 47);push(head, 16);push(head, 12);push(head, 14);/* function to print the result*/var res = check_pair_sum(head, 26);if (res == false) document.write("NO PAIR EXIST");</script> |
Output
14 12
Time complexity: O(n*n)
Auxiliary Space: O(1)
Method 2 (using hashing):
- Take a hashtable and mark all element with zero
- Iteratively mark all the element as 1 in hashtable which are present in linked list
- Iteratively find sum-current element of linked list is present in hashtable or not
Implementation:
C++
// CPP program to for finding the pair with given sum#include <bits/stdc++.h>#define MAX 100000using namespace std;/* Link list node */struct Node { int data; struct Node* next;};/* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */void push(struct Node** head_ref, int new_data){ /* allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node;}/* Takes head pointer of the linked list and sum*/bool check_pair_sum(struct Node* head, int sum){ unordered_set<int> s; struct Node* p = head; while (p != NULL) { int curr = p->data; if (s.find(sum - curr) != s.end()) { cout << curr << " " << sum - curr; return true; } s.insert(p->data); p = p->next; } return false;}/* Driver program to test above function*/int main(){ /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct linked list */ push(&head, 1); push(&head, 4); push(&head, 1); push(&head, 12); push(&head, 1); push(&head, 18); push(&head, 47); push(&head, 16); push(&head, 12); push(&head, 14); /* function to print the result*/ bool res = check_pair_sum(head, 26); if (res == false) cout << "NO PAIR EXIST"; return 0;} |
Java
// Java program for finding// the pair with given sumimport java.util.*;class GFG { static int MAX = 100000; /* Link list node */ static class Node { int data; Node next; }; static Node head; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ static void push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list of the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; head = head_ref; } /* Takes head pointer of the linked list and sum*/ static boolean check_pair_sum(Node head, int sum) { HashSet<Integer> s = new HashSet<Integer>(); Node p = head; while (p != null) { int curr = p.data; if (s.contains(sum - curr)) { System.out.print(curr + " " + (sum - curr)); return true; } s.add(p.data); p = p.next; } return false; } // Driver Code public static void main(String[] args) { /* Start with the empty list */ head = null; /* Use push() to construct linked list */ push(head, 1); push(head, 4); push(head, 1); push(head, 12); push(head, 1); push(head, 18); push(head, 47); push(head, 16); push(head, 12); push(head, 14); /* function to print the result*/ boolean res = check_pair_sum(head, 26); if (res == false) System.out.print("NO PAIR EXIST"); }}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to for finding the pair with given sumMAX = 100000''' Link list node '''class Node: def __init__(self, data): self.data = data self.next = None''' Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. '''def push(head_ref, new_data): ''' allocate node ''' new_node = Node(new_data) ''' put in the data ''' new_node.data = new_data ''' link the old list of the new node ''' new_node.next = (head_ref) ''' move the head to point to the new node ''' (head_ref) = new_node return head_ref''' Takes head pointer of the linked list and sum'''def check_pair_sum(head, sum): s = set() p = head while (p != None): curr = p.data if((sum - curr) in s): print(curr, end=' ') print(sum-curr, end='') return True s.add(p.data) p = p.next return False''' Driver program to test above function'''if __name__ == '__main__': ''' Start with the empty list ''' head = None ''' Use push() to construct linked list ''' head = push(head, 1) head = push(head, 4) head = push(head, 1) head = push(head, 12) head = push(head, 1) head = push(head, 18) head = push(head, 47) head = push(head, 16) head = push(head, 12) head = push(head, 14) ''' function to print the result''' res = check_pair_sum(head, 26) if (res == False): print("NO PAIR EXIST")# This code is contributed by rutvik_56 |
C#
// C# program for finding// the pair with given sumusing System;using System.Collections.Generic;class GFG { static int MAX = 100000; /* Link list node */ public class Node { public int data; public Node next; }; static Node head; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ static void push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list of the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; head = head_ref; } /* Takes head pointer of the linked list and sum*/ static Boolean check_pair_sum(Node head, int sum) { HashSet<int> s = new HashSet<int>(); Node p = head; while (p != null) { int curr = p.data; if (s.Contains(sum - curr)) { Console.Write(curr + " " + (sum - curr)); return true; } s.Add(p.data); p = p.next; } return false; } // Driver Code public static void Main(String[] args) { /* Start with the empty list */ head = null; /* Use push() to construct linked list */ push(head, 1); push(head, 4); push(head, 1); push(head, 12); push(head, 1); push(head, 18); push(head, 47); push(head, 16); push(head, 12); push(head, 14); /* function to print the result*/ Boolean res = check_pair_sum(head, 26); if (res == false) Console.Write("NO PAIR EXIST"); }}// This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program for finding // the pair with given sum const MAX = 100000; /* Link list node */ class Node { constructor() { this.data = 0; this.next = null; } } var head = null; /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ function push(head_ref, new_data) { /* allocate node */ var new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list of the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; head = head_ref; } /* Takes head pointer of the linked list and sum*/ function check_pair_sum(head, sum) { var s = new Set(); var p = head; while (p != null) { var curr = p.data; if (s.has(sum - curr)) { document.write(curr + " " + (sum - curr)); return true; } s.add(p.data); p = p.next; } return false; } // Driver Code /* Start with the empty list */ head = null; /* Use push() to construct linked list */ push(head, 1); push(head, 4); push(head, 1); push(head, 12); push(head, 1); push(head, 18); push(head, 47); push(head, 16); push(head, 12); push(head, 14); /* function to print the result*/ var res = check_pair_sum(head, 26); if (res == false) document.write("NO PAIR EXIST"); // This code is contributed by rdtank. </script> |
Output
12 14
Time complexity: O(n)
Auxiliary Space: O(n)
Method 3 (using recursion):
Traverse through each node and find if element Sum-(node->data) is available in remaining linked list or not. If not, current node will not be a part of solution. For each node the list is traversed a single time. So, the overall time complexity is quadratic, but no additional space is required for this solution. Although we are using additional stack space for recursion.
Implementation:
C++
// C++ implementation of the above approach#include<bits/stdc++.h>using namespace std;/* Link list node */struct Node { int data; struct Node* next;}; void push(struct Node** head_ref, int new_data){ struct Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;} bool findElement(struct Node* head, int element){ if (head == NULL) { return false; } else if (head->data == element) { return true; } return findElement(head->next, element);} bool check_pair_sum(struct Node* head, int sum){ bool found = false; while (head != NULL) { found = findElement(head, sum - head->data); if (found == true) { cout<<head->data<<" and "<<(sum-head->data); return found; } head = head->next; } return found;} // Driver Codeint main(){ /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct linked list*/ push(&head, 1); push(&head, 4); push(&head, 1); push(&head, 12); push(&head, 1); push(&head, 18); push(&head, 47); push(&head, 16); push(&head, 12); push(&head, 14); push(&head, 0); /* Function to print the result*/ bool res = check_pair_sum(head, 26); if (res == false) cout<<"No pair found"; return 0;}// This code is contributed by Yash Agarwal(yashagarwal2852002) |
C
// C++ implementation of the above approach#include <stdbool.h>#include <stdio.h>#include <stdlib.h>/* Link list node */struct Node { int data; struct Node* next;};void push(struct Node** head_ref, int new_data){ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}bool findElement(struct Node* head, int element){ if (head == NULL) { return false; } else if (head->data == element) { return true; } return findElement(head->next, element);}bool check_pair_sum(struct Node* head, int sum){ bool found = false; while (head != NULL) { found = findElement(head, sum - head->data); if (found == true) { printf("%d and %d \n", head->data, sum - head->data); return found; } head = head->next; } return found;}// Driver Codeint main(){ /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct linked list*/ push(&head, 1); push(&head, 4); push(&head, 1); push(&head, 12); push(&head, 1); push(&head, 18); push(&head, 47); push(&head, 16); push(&head, 12); push(&head, 14); push(&head, 0); /* Function to print the result*/ bool res = check_pair_sum(head, 26); if (res == false) printf("No pair found"); return 0;} |
Java
// Java implementation of the above approach// Node classclass Node { int data; Node next; Node(int data) { this.data = data; this.next = null; }}// Function to add new node at the beginningclass LinkedList { static Node push(Node head_ref, int new_data) { Node new_node = new Node(new_data); new_node.next = head_ref; head_ref = new_node; return head_ref; }}// Function to find an element in the linked listclass Search { static boolean findElement(Node head, int element) { if (head == null) { return false; } else if (head.data == element) { return true; } return findElement(head.next, element); }}// Function to check if there exists a pair with given sumclass PairSum { static boolean check_pair_sum(Node head, int sum) { boolean found = false; while (head != null) { found = Search.findElement(head, sum - head.data); if (found == true) { System.out.println(head.data + " and " + (sum - head.data)); return found; } head = head.next; } return found; }}// Driver codeclass Main { public static void main(String[] args) { // Start with the empty list Node head = null; // Use push() to construct linked list head = LinkedList.push(head, 1); head = LinkedList.push(head, 4); head = LinkedList.push(head, 1); head = LinkedList.push(head, 12); head = LinkedList.push(head, 1); head = LinkedList.push(head, 18); head = LinkedList.push(head, 47); head = LinkedList.push(head, 16); head = LinkedList.push(head, 12); head = LinkedList.push(head, 14); head = LinkedList.push(head, 0); // Function to print the result boolean res = PairSum.check_pair_sum(head, 26); if (res == false) System.out.println("No pair found"); }}// This code is contributed by divyansh2212 |
Python3
# Python implementation of the above approach# Node classclass Node: def __init__(self, data): self.data = data self.next = None# Function to add new node at the beginningdef push(head_ref, new_data): new_node = Node(new_data) new_node.next = head_ref head_ref = new_node return head_ref# Function to find an element in the linked listdef findElement(head, element): if (head == None): return False elif (head.data == element): return True return findElement(head.next, element)# Function to check if there exists a pair with given sumdef check_pair_sum(head, sum): found = False while (head != None): found = findElement(head, sum - head.data) if (found == True): print(head.data, "and", (sum - head.data)) return found head = head.next return found# Driver codeif __name__ == '__main__': # Start with the empty list head = None # Use push() to construct linked list head = push(head, 1) head = push(head, 4) head = push(head, 1) head = push(head, 12) head = push(head, 1) head = push(head, 18) head = push(head, 47) head = push(head, 16) head = push(head, 12) head = push(head, 14) head = push(head, 0) # Function to print the result res = check_pair_sum(head, 26) if (res == False): print("No pair found") |
C#
using System;public class LinkedList{ /* Link list node */ public class Node { public int data; public Node next; } public static void Push(ref Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; } public static bool FindElement(Node head, int element) { if (head == null) { return false; } else if (head.data == element) { return true; } return FindElement(head.next, element); } public static bool CheckPairSum(Node head, int sum) { bool found = false; while (head != null) { found = FindElement(head, sum - head.data); if (found == true) { Console.WriteLine(head.data + " and " + (sum - head.data)); return found; } head = head.next; } return found; } // Driver Code public static void Main() { /* Start with the empty list */ Node head = null; /* Use Push() to construct linked list*/ Push(ref head, 1); Push(ref head, 4); Push(ref head, 1); Push(ref head, 12); Push(ref head, 1); Push(ref head, 18); Push(ref head, 47); Push(ref head, 16); Push(ref head, 12); Push(ref head, 14); Push(ref head, 0); /* Function to print the result*/ bool res = CheckPairSum(head, 26); if (res == false) Console.WriteLine("No pair found"); }} |
Javascript
Javascript// Javascript program of the above approach// link list nodeclass Node{ constructor(data){ this.data = data; this.next = null; }}function push(head_ref, new_data){ let new_node = new Node(new_data); new_node.next = head_ref; // head_ref = new_node; return new_node;}function findElement(head, element){ if(head == null) return false; else if(head.data == element) return true; return findElement(head.next, element);}function check_pair_sum(head, sum){ let found = false; while(head != null){ found = findElement(head, sum - head.data); if(found == true){ document.write(head.data + " and " + (sum-head.data)); return found; } head = head.next; } return found;}// driver code// start with empty listlet head = null;head = push(head, 1);head = push(head, 4);head = push(head, 1);head = push(head, 12);head = push(head, 1);head = push(head, 18);head = push(head, 47);head = push(head, 16);head = push(head, 12);head = push(head, 14);head = push(head, 0);// function to print the resultlet res = check_pair_sum(head, 26);if(res == false) document.write("No pair found");// this code is contributed by Kirti Agarwal |
Output
14 and 12
Time complexity: O(n ^ 2)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
