## Twitter Interview Question for Software Engineer Interns

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 6 vote

Add all the numbers in the array = r1.
calculate sum of n natural numbers using n*(n+1)/2 = r2
substract r1 from r2 you will get the result

Comment hidden because of low score. Click to expand.
7

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

Comment hidden because of low score. Click to expand.
0

One-liner in ruby:

``````def find_missing(arr, n)
arr.reduce(:^) ^ (1..n).reduce(:^)
end``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Add All the number of given array
Let's say it's sum is K

Now we know , {1,2,3,4,5,......n} is an Arithmetic series with a = 1, d = 1

it's sum is K' = (n x (n+1) / 2)

Now the missing element can easily be obtained from subtracting K from K'
i.e. missing number/element = K' - K

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

sorting the array is O(log(n)) though

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

}``````

Comment hidden because of low score. Click to expand.
0

The array isn't sorted already I thought.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why do you want to work with arrays? Not a good idea. You should represent numbers as link lists and write an operation sum two numbers and you're just fine even with large numbers.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Method: plus 1 to n named SUM : n*(n-1)/2
SUM - sum of array -> result

2. Method: scan num-> arr[num]*=-1(num = n will do nothing)
scan second time -> find the positive num -> if have then the index is missing
-> if don't have , then n is missing

Comment hidden because of low score. Click to expand.
0
of 0 vote

make an array of bool with size of n, initialize all to false, mark boolArray[i] = true if you find the ith number in the original array. run through the bool one last time to figure which index has false. you will get your number. O(n) solution

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ public int findMissing(int n, int[] arr) { int sum = (n * (n - 1)) / 2; for (int i : arr) sum -= i; return sum; } }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java O(n) time, O(1) space

``````public int findMissing(int n, int[] arr) {
int sum = (n * (n - 1)) / 2;
for (int i : arr)
sum -= i;
return sum;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````# 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]))``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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);

Comment hidden because of low score. Click to expand.
0

for sorting you are using two for loops. Which in worst case takes the time complexity O(N^2).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.