Given an array arr[] of non-negative integers, let’s define X as the XOR of all the array elements and S as the sum of all the array elements. The task is to find two elements such that when they are appended to the array S = 2 * X is satisfied for the updated array.
Examples:
Input: arr[] = {1, 7}
Output: 6 14
Initially S = 8, and X = 6. After appending 6
and 14, S_NEW = (8 + 6 + 14) = 28
and X_NEW = (6 ^ 6 ^ 14) = 14
Clearly, S_NEW = 2 * X_NEW
Input: arr[] = {1, 3}
Output: 2 6
Naive approach: Run two nested loops from 1 to S and check for each pair whether it satisfies the condition or not. This will take O(S2) time.
Efficient approach: It can be observed that if X and S + X are appended to the array then S_NEW = 2 * (S + X) and X_NEW = S + X which satisfy the given condition.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find the required numbersvoid findNums(int arr[], int n){ // Find the sum and xor int S = 0, X = 0; for (int i = 0; i < n; i++) { S += arr[i]; X ^= arr[i]; } // Print the required elements cout << X << " " << (X + S);}// Driver codeint main(){ int arr[] = { 1, 7 }; int n = sizeof(arr) / sizeof(int); findNums(arr, n); return 0;} |
Java
// Java implementation of the approach class GFG { // Function to find the required numbers static void findNums(int arr[], int n) { // Find the sum and xor int S = 0, X = 0; for (int i = 0; i < n; i++) { S += arr[i]; X ^= arr[i]; } // Print the required elements System.out.println(X + " " + (X + S)); } // Driver code public static void main (String[] args) { int arr[] = { 1, 7 }; int n = arr.length; findNums(arr, n); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to find the required numbers def findNums(arr, n) : # Find the sum and xor S = 0; X = 0; for i in range(n) : S += arr[i]; X ^= arr[i]; # Print the required elements print(X, X + S); # Driver code if __name__ == "__main__" : arr = [ 1, 7 ]; n = len(arr); findNums(arr, n); # This code is contributed by AnkiRai01 |
C#
// C# implementation of the approach using System;class GFG { // Function to find the required numbers static void findNums(int []arr, int n) { // Find the sum and xor int S = 0, X = 0; for (int i = 0; i < n; i++) { S += arr[i]; X ^= arr[i]; } // Print the required elements Console.WriteLine(X + " " + (X + S)); } // Driver code public static void Main() { int []arr = { 1, 7 }; int n = arr.Length; findNums(arr, n); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// javascript implementation of the approach // Function to find the required numbers function findNums(arr , n) { // Find the sum and xor var S = 0, X = 0; for (i = 0; i < n; i++) { S += arr[i]; X ^= arr[i]; } // Print the required elements document.write(X + " " + (X + S)); } // Driver code var arr = [ 1, 7 ]; var n = arr.length; findNums(arr, n);// This code contributed by gauravrajput1 </script> |
6 14
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
