Given an array arr[] of size N, each integer from the range [1, N] appears exactly once except A which appears twice and B which is missing. The task is to find the numbers A and B.
Examples:
Input: arr[] = {1, 2, 2, 3, 4}
Output:
A = 2
B = 5
Input: arr[] = {5, 3, 4, 1, 1}
Output:
A = 1
B = 2
Approach: From the sum of first N natural numbers,
SumN = 1 + 2 + 3 + … + N = (N * (N + 1)) / 2
And, let the sum of all the array elements be Sum. Now,
SumN = Sum – A + B
A – B = Sum – SumN …(equation 1)
And from the sum of the squares of first N natural numbers,
SumSqN = 12 + 22 + 32 + … + N2 = (N * (N + 1) * (2 * n + 1)) / 6
And, let the sum of the squares of all the array elements be SumSq. Now,
SumSq = SumSqN + A2 – B2
SumSq – SumSqN = (A + B) * (A – B) …(equation 2)
Put value of (A – B) from equation 1 in equation 2,
SumSq – SumSqN = (A + B) * (Sum – SumN)
A + B = (SumSq – SumSqN) / (Sum – SumN) …(equation 3)
Solving equation 1 and equation 3 will give,
B = (((SumSq – SumSqN) / (Sum – SumN)) + SumN – Sum) / 2
And, A = Sum – SumN + B
Below is the implementation of the above approach:
C++
//C++ implementation of the approach#include <cmath>#include<bits/stdc++.h>#include <iostream>using namespace std; // Function to print the required numbers void findNumbers(int arr[], int n) { // Sum of first n natural numbers int sumN = (n * (n + 1)) / 2; // Sum of squares of first n natural numbers int sumSqN = (n * (n + 1) * (2 * n + 1)) / 6; // To store the sum and sum of squares // of the array elements int sum = 0, sumSq = 0, i; for (i = 0; i < n; i++) { sum += arr[i]; sumSq = sumSq + (pow(arr[i], 2)); } int B = (((sumSq - sumSqN) / (sum - sumN)) + sumN - sum) / 2; int A = sum - sumN + B; cout << "A = " ; cout << A << endl; cout << "B = " ; cout << B << endl; } // Driver codeint main() { int arr[] = { 1, 2, 2, 3, 4 }; int n = sizeof(arr)/sizeof(arr[0]); findNumbers(arr, n); return 0;} |
Java
// Java implementation of the approachpublic class GFG { // Function to print the required numbers static void findNumbers(int arr[], int n) { // Sum of first n natural numbers int sumN = (n * (n + 1)) / 2; // Sum of squares of first n natural numbers int sumSqN = (n * (n + 1) * (2 * n + 1)) / 6; // To store the sum and sum of squares // of the array elements int sum = 0, sumSq = 0, i; for (i = 0; i < n; i++) { sum += arr[i]; sumSq += Math.pow(arr[i], 2); } int B = (((sumSq - sumSqN) / (sum - sumN)) + sumN - sum) / 2; int A = sum - sumN + B; System.out.println("A = " + A + "\nB = " + B); } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 2, 3, 4 }; int n = arr.length; findNumbers(arr, n); }} |
Python3
# Python3 implementation of the approachimport math# Function to print the required numbersdef findNumbers(arr, n): # Sum of first n natural numbers sumN = (n * (n + 1)) / 2; # Sum of squares of first n natural numbers sumSqN = (n * (n + 1) * (2 * n + 1)) / 6; # To store the sum and sum of squares # of the array elements sum = 0; sumSq = 0; for i in range(0,n): sum = sum + arr[i]; sumSq = sumSq + (math.pow(arr[i], 2)); B = (((sumSq - sumSqN) / (sum - sumN)) + sumN - sum) / 2; A = sum - sumN + B; print("A = ",int(A)) ; print("B = ",int(B)); # Driver codearr = [ 1, 2, 2, 3, 4 ];n = len(arr);findNumbers(arr, n);#This code is contributed by Shivi_Aggarwal |
C#
// C# implementation of the approach using System;public class GFG { // Function to print the required numbers static void findNumbers(int []arr, int n) { // Sum of first n natural numbers int sumN = (n * (n + 1)) / 2; // Sum of squares of first n natural numbers int sumSqN = (n * (n + 1) * (2 * n + 1)) / 6; // To store the sum and sum of squares // of the array elements int sum = 0, sumSq = 0, i; for (i = 0; i < n; i++) { sum += arr[i]; sumSq += (int)Math.Pow(arr[i], 2); } int B = (((sumSq - sumSqN) / (sum - sumN)) + sumN - sum) / 2; int A = sum - sumN + B; Console.WriteLine("A = " + A + "\nB = " + B); } // Driver code public static void Main() { int []arr = { 1, 2, 2, 3, 4 }; int n = arr.Length; findNumbers(arr, n); } } // This code is contributed by PrinciRaj1992 |
PHP
<?php// PHP implementation of the approach// Function to print the required numbers function findNumbers($arr, $n) { // Sum of first n natural numbers $sumN = ($n * ($n + 1)) / 2; // Sum of squares of first n // natural numbers $sumSqN = ($n * ($n + 1) * (2 * $n + 1)) / 6; // To store the sum and sum of // squares of the array elements $sum = 0 ; $sumSq = 0 ; for ($i = 0; $i < $n; $i++) { $sum += $arr[$i]; $sumSq += pow($arr[$i], 2); } $B = ((($sumSq - $sumSqN) / ($sum - $sumN)) + $sumN - $sum) / 2; $A = $sum - $sumN + $B; echo "A = ", $A, "\nB = ", $B;} // Driver code $arr = array( 1, 2, 2, 3, 4 );$n = sizeof($arr) ; findNumbers($arr, $n); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of the approach// Function to print the required numbersfunction findNumbers(arr, n){ // Sum of first n natural numbers sumN = (n * (n + 1)) / 2; // Sum of squares of first n // natural numbers sumSqN = (n * (n + 1) * (2 * n + 1)) / 6; // To store the sum and sum of // squares of the array elements let sum = 0 ; let sumSq = 0 ; for (let i = 0;i < n; i++) { sum += arr[i]; sumSq += Math.pow(arr[i], 2); } B = (((sumSq - sumSqN) / (sum - sumN)) + sumN - sum) / 2; A = sum - sumN + B; document.write( "A = "+ A, "<br>B = ", B);}// Driver codelet arr = [ 1, 2, 2, 3, 4 ];n = arr.length ;findNumbers(arr, n);// This code is contributed// by bobby</script> |
A = 2 B = 5
Time Complexity: O(N), since the loop runs from 0 to (n – 1).
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
