Linked List Pair Sum
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 sum import 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 sum import math import 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 sum def 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 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 Vikash Kumar 37 |
C#
// C# code to find the pair with given sum using 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 beginning 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 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> |
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 100000 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*/ 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 sum import 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 sum MAX = 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 sum using 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> |
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 Code 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); 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 Code 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); 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 class class Node { int data; Node next; Node( int data) { this .data = data; this .next = null ; } } // Function to add new node at the beginning class 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 list class 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 sum class 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 code class 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 class class Node: def __init__( self , data): self .data = data self . next = None # Function to add new node at the beginning def 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 list def 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 sum def 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 code 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 ) 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 node class 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 list let 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 result let res = check_pair_sum(head, 26); if (res == false ) document.write( "No pair found" ); // this code is contributed by Kirti Agarwal |
14 and 12
Time complexity: O(n ^ 2)
Auxiliary Space: O(n)
Contact Us