Twitter Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
you are right bro...your solution is true ..but what if i say integer sizes goes beyond limit..than it will not work..:)
solution for that will be ..=====
1.) XOR all no.s from 1 to n.let XOR be X
2) .XOR all array elements .let say XOR be Y
3) X xor Y is our answer
The previous answers are definitely the way you would want to solve the problem, but when n is large, if you're not able to use a BigInt library you would need to do it another way.
You could sort the array, call it A, and then compute A[i+1]-A[i] until you find the value 2...in which case you're missing A[i]+1.
If you choose to count sort your list of numbers into array A, you simply find the index i for which A[i]=0.
use Binary search
BinarySearch(int a[],int low,int high)
{
mid=(low+high)/2
if(low < high) return -1;
else if(a[mid-1]==(mid-1) && a[mid]==(mid+1)) return mid;
else if (a[low]==low) BinarySearch(a,mid+1,high)
else if (a[high]==high) BinarySearch(a,low,mid+1)
}
Solution in O(n)
/*
You have n - 1 numbers from 1 to n. Your task is to find the missing number.
I.e.
n = 5
v = [4, 2, 5, 1]
The result is 3.
*/
#include <iostream>
#include <vector>
int sum_of_sequential(std::vector<int>& vec) {
auto begin = vec.begin();
auto end = vec.end() - 1;
int res = *end - *begin;
res++;
return ((res * (res + 1))/2);
}
int sum_of_elements(std::vector<int>&vec) {
int sum = 0;
for(int i : vec)
sum += i;
return sum;
}
int main() {
std::vector<int> vec{1, 2, 4, 5};
int sum = sum_of_sequential(vec);
int tot = sum_of_elements(vec);
std::cout << sum - tot << std::endl;
}
We can use the summation equation for a sorted array with values from 1-n to find the intended sum and subtract the actual sum from that value to find our answer.
var arr = [1, 2, 3, 5, 6, 7, 8, 9, 10]; //4 is the missing value
function findMissing(arr){
//Calculate the sum of the intended amount using the summation equation
var max = arr.length + 1;
var sum = (max * (max + 1))/2;
//Calculate the sum of all actual elements
var actualSum = 0;
for(var i = 0 ; i < arr.length; i++){
actualSum += arr[i];
}
//Return the difference of the two to find the missing element.
return sum - actualSum;
}
The above example works for an array with sorted values from 1-n, but what if we have an unsorted array with values from 10-n? We can use the summation equation again to normalize the values of the intended sum. Once we find that value, we simply subtract the actaul sum from that value and we have our missing element.
var unSortedArr = [11, 13, 14, 16, 10, 17, 19, 18, 20, 12]; //Min is 10 and max is 20
function unsortedFindMissing(unSortedArr, max, min){
//Get the amount to subtract from the actual sum by normalizing (e.g from 10-20 to 1-10)
//Use the sumation equation to find the amount to subtract
var sum = ((max*(max+1))/ 2) - ((min*(min-1))/2);
//Calculate the sum of the actual elements
var actualSum = 0;
for(var i = 0; i < unSortedArr.length; i++){
actualSum += unSortedArr[i];
}
return sum - actualSum;
}
public class FindMissingNumber {
private FindMissingNumber() {
}
// does not work for zero.
public static int findMissingNumber(int[] inputArray) {
int xor1 = 1;
int xor2 = inputArray[0];
int length = inputArray.length;
for (int i = 2; i <= length + 1; i++) {
xor1 = xor1 ^ i;
}
for (int i = 1; i < length; i++) {
xor2 = xor2 ^ inputArray[i];
}
return xor1 ^ xor2;
}
// does not work for zero.
public static int findMissingNumberUsingFormula(int[] inputArray) {
int sum = 0;
for (int i : inputArray) {
sum = i + sum;
}
// actual size of array is length + 1 since one number is missing.
int length = inputArray.length + 1;
int factor = length * (length + 1) / 2;
return factor - sum;
}
}
This solution works for finding 1 or more than one missing number in the input array. Input doesn't have to be given sorted.
Running Time: O(n)
Space: Extra HashSet needed
public static void find_missing_number2(Integer[] v){
if(v.length < 1) {
System.out.println("No values provided in input integer");
System.out.println();
return;
}
System.out.println("The missing number(s) is/are: ");
HashSet<Integer> hs = new HashSet<Integer>();
for(int i : v)
hs.add(i);
int maxN = v[0];
int minN = v[0];
for(int i : v){
if(i > maxN) maxN = i;
if(i < minN) minN = i;
}
boolean missing = false;
for(int j = minN; j <= maxN; j++){
if(!(hs.contains(j))){
missing = true;
System.out.println(j);
}
}
if(!missing) System.out.println("There are no missing numbers in the input array");
System.out.println();
}
public static void main(String[] args){
//some rudimentary testing
Integer[] b = new Integer[0];
Integer[] vv = new Integer[]{5, 3, 2, 1};
Integer[] v = new Integer[]{2, 3, 5, 9};
Integer[] c = new Integer[]{0, 3, 2, 1};
find_missing_number2(b);
find_missing_number2(vv);
find_missing_number2(v);
find_missing_number2(c);
}
Output:
No values provided in input integer
The missing number(s) is/are:
4
The missing number(s) is/are:
4
6
7
8
The missing number(s) is/are:
There are no missing numbers in the input array
/*
Karumanchi book: Searching, Problem 13-17 Find the missing number
Given a list of n - 1 integers in the range of 1 to n. No duplicates in list.
Ex. input: [1, 2, 4, 6, 3, 7, 8] output: 5
Regular solution:
1. Get the sum of numbers, sum = n * (n + 1) / 2
2. Subtract all the numbers from sum and you will get the missing number
O(n) time complexity
XOR solution for when the numbers go beyond the max allowed integer range:
1. XOR all the array elements, let the result of XOR be X
2. XOR all numbers from 1 to n. Let XOR be Y.
3. XOR of X and Y gives the missing number
Time complexity O(n), space complexity O(1)
*/
public static int findMissingNumber(int[] numbers, int number)
{
int X = 0, Y = 0;
int i;
for (i = 0; i < numbers.length; i++)
{
X ^= numbers[i];
}
for (i = 1; i <= number; i++)
{
Y ^= i;
}
return X ^ Y;
}
2 Implementations in Java, one with O(nlogn) and one with O(n)
import java.util.Arrays;
public class FindTheMissingNumber {
public static void main(String[] args) {
int[] a = { 4, 2, 5, 1 };
System.out.print(new FindTheMissingNumber().find(a, 5));
System.out.print(new FindTheMissingNumber().find(5, a));
}
// O(nlogn)
public int find(int[] numbers, int size) {
Arrays.sort(numbers);
for (int i = 0; i < size - 1; i++) {
if (numbers[i + 1] != numbers[i] + 1) {
return numbers[i] + 1;
}
}
return 0;
}
// O(n)
public int find(int size, int[] numbers) {
int number = (size + 1) * size / 2;
for (int i = 0; i < size - 1; i++) {
number -= numbers[i];
}
return number;
}
}
# Assuming n is integer and there is only 1 missing number
# Python 3.4
def find_missing_num(n, v):
v = sorted(v)
for number in range(1, n+1):
if number == v[number - 1]:
continue
else:
return number
#test
print(find_missing_num(5, [4,2,5,1]))
print(find_missing_num(10, [4,2,5,3,9,6,8,1]))
hi sir am sashikumar ......am providing the sample of code here......
my code divided into two block.block one for sorting and another for finding missing ele....
int missele(int a[],int n)
{
for(i=0;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
}
}
}
/* now am finding missing ele*/
for(i=0;i<n;i++)
{
if((a[i]+1)==a[i+1])
{
pf("")
}
else
pf("%d",a[i]+1);
Add all the numbers in the array = r1.
- kishore25kumar December 11, 2013calculate sum of n natural numbers using n*(n+1)/2 = r2
substract r1 from r2 you will get the result