#### Array contains continuous numbers from 1 to n. One number is deleted and one number is repeated. Find the missing number and the repeated one

**rahul**-

**Last updated:**Sunday, September 21, 2014

Here we have to find the missing number and the repeated number from the list of numbers from 1 to n

For example: 1 2 3 4 5 6 7 8 9 10

Now we removed 7 and repeated 4 as below

1 2 3 4 5 6 4 8 9 10

The solution of this question can be done using mathematics. In mathematics we have studied the formula to get the sum of 1 to n as below

n*(n+1)/2

so sum of 1 to 10 will be 10*11/2 = 55

Now jump to the question to find missing number and the repeated number we will make use of mathematical equations

Traverse the array and get the sum of (1 2 3 4 5 6 4 8 9 10) = 52

Let “r” = repeated number and let “m” = missing number

n(n+1)/2 – m +r = 52

m – r = 3 ———– Eq 1

Multiplication of 1 to n will be factorial of n

But since “m” is missing and “r” is repeated so the second equation will be

n!*r/m = 1*2*3*4*5*6*4*8*9*10

7*r/m = 4 —————- Eq 2

By using Eq 1 and Eq 2 we will get

r = 4 and m = 7

If you know another better solution to solve this then write your answer below

#### Find number of swaps needed to Arrange all 0’s on the first half and all 1’s on the second half of the array

**rahul**-

**Last updated:**Sunday, September 21, 2014

In this question we have to find the number of swaps required to move all zeros (0) at one end and all ones (1) on the other end of the array. For example if the array contains

0 1 1 0 0 0 1 0 0 1 0

Then you should make this as below

0 0 0 0 0 0 0 1 1 1 1

We can make an algorithm what if left element is zero(0) and right element is one(1) then Don’t Swap.

If both are zero(0) then move one step ahead till you find one(1)

If left element is one(1) and right element is zero(0) then Swap(Arr[i], Arr[j])

If you will follow above steps then finally all zeros will be at first half and all ones will be on the second half.

Below is the code snippet of above algorithm

1 2 3 4 5 6 7 8 9 |
int iSwapCount = 0; for(int i = 0; i < len; i++) { for(int j = 0; j < len-1; j++) { if(arr[j] == 1 && arr[j+1] == 0) { swap(arr[j], arr[j+1]); iSwapCount++; } } } |

If you have some other awesome idea then please share it below in comment area.

#### Arrange all 0’s on the first half and all 1’s on the second half of the array

**rahul**-

**Last updated:**Sunday, September 21, 2014

In this question you have to move all zeros (0) at one end and all ones (1) on the other end of the array. For example if the array contains

0 1 1 0 0 0 1 0 0 1 0

Then you should make this as below

0 0 0 0 0 0 0 1 1 1 1

**Algorithm in O(n)**

Take two variables **i** and **j**. Point **i** at start of array and point **j** at end of array

If Arr[i] == 0 then Increment **i**

If Arr[j] == 1 then Decrement **j**

If (Arr[i] == 1 and Arr[j] == 0) then Swap (Arr[i], Arr[j])

if(i == j) then Stop the loop

If you know better solution than this then write is down in comment area.

#### Find the common numbers from Two Arrays containing integers

**rahul**-

**Last updated:**Sunday, September 21, 2014

This is a common interview question. In this question we have 2 arrays which contains integers (numbers). We have to find the common integers (numbers) between the two arrays.

We will take a HashTable and will insert all the numbers from first array into it. Now traverse the second array and before inserting into hashtable check if number already present in hash then this number is the common between two arrays.

Time Complexity O(n+m) where n and m are the number of elements in first and second array respectively.

Space Complexity O(n+m)

If you know better solution than this then write your solution below in Facebook comment area.

#### Arrange Even position numbers in Ascending and Odd position numbers in Descending order in an array

**rahul**-

**Last updated:**Thursday, September 18, 2014

In this question we need to arrange the numbers which are occurring at Even positions in ascending order and Odd position numbers in descending order.

The solution is simple,

Traverse the array from front in alternate even positions and arrange elements in ascending order using Quick sort

Traverse the array from backward in alternate positions and arrange elements in ascending order using Quick sort (Second step I intentionally meant, ascending, because if we will see from Front odd position elements will be in descending order)

Example: **1**, 7, **13**, 3, **5**, 6, **11**, 2, **4**, 7

Output: **13**, 2, **11**, 3, **5**, 6, **4**, 7, **1**, 7

If you know better or other method than this then please let us know. Write your solution below.

#### Expand the Array from [a2b3c4d2] to [aabbbccccdd] in O(n) and O(1) Space

**rahul**-

**Last updated:**Thursday, September 18, 2014

Given an array of length 11 which contains items as [a2b3c4d2] we need to expand it to [aabbbccccdd]

The best solution I know is that start reading array from back and write it down from back of an array as I have shown below.

Take 2 pointers, Point first pointer at **“d2″** and second at end of an array.

Start with d2 and last position (marked with Green arrow).

Read as **“d”** has to be inserted **“2”** times, Now move second pointer from back two times and insert **“d”**. Now move First pointer one time and now it will point at **“c4″.**

Repeat the step till both the pointers point to each other

This method wont take more than O(n) time and O(1) Space complexity.

If you know better or other method than this then please let us know. Write your solution below.

#### Find the Largest number which can be formed from a given numbers in an array

**rahul**-

**Last updated:**Thursday, September 18, 2014

We need to find the greatest number from the elements of an array.

For Example: **Array = 2, 3, 9, 4**

Solution is Arrange elements of an array in descending order like **9,4,3,2** and this is the largest number.

If you know the better solution then write it down in the Comments below

#### Tell me about yourself

**rahul**-

**Last updated:**Thursday, September 18, 2014

Assume that you are sitting in front of the HR manager. Take the initiative to attend this question and tell your real answers.

Post your answer in Facebook box below.

#### Get the number with maximum repetitions in a sorted array of integers

**rahul**-

**Last updated:**Thursday, August 28, 2014

This question is very common question. Given a sorted array of integers, write a function that will return the number with the biggest or maximum number of repetitions. This means that we have to find the number with the maximum repetition in a sorted array of numbers. So we need to write an algorithm to find maximum number of repetition of a number in a sorted array.

There can be various ways to do this. I am mentioning two methods to implement this.

Method1: O(n)

Method2: Less than O(n) by using jumping logic.

Implementation of Method1 is below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
void Method1() { g_iMaxCount = 0; g_iMaxNumber = 0; // Place your logic here int iCount = 0; int iNumber = g_pValues[0]; int i = 0; for(int i=0; i<g_uiArrayLength;i++) { if(iNumber!=g_pValues[i]) { if(g_iMaxCount<iCount) { g_iMaxCount = iCount; g_iMaxNumber = iNumber; } iCount=0; iNumber = g_pValues[i]; } iCount++; } //if last element is Greater if(g_iMaxCount<iCount) { g_iMaxCount = iCount; g_iMaxNumber = iNumber; } } |

Method2 is based on jumping logic. In this algorithm we will first traverse the array till the first element is encountering. We will maintain the count of occurrence of first element. Now as we know that first number occurred N number of times then we will jump N steps till second number of array is occurring. We will jump in multiple of N, let M times. If we are encountering third number then we will step back one by one till we are getting second number of the array, let S is the number of steps we have taken back.

So second number’s occurrence can be calculated as below formula

### Number of Occurrence = (M*N) – S

Now if we will reach to some point where remaining number of elements in an Array is less than Number of Occurrence of some number then we can skip traversing the array.

Implementation of Method2 is below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
void Method2() { //int iArray[25] = {2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3,4,5}; int iCount = 0; int iNumber = g_pValues[0]; int i = 0; int iCurrCount = 0; int iCountLeft = 0; //Initial Traverse array till Same Value coming while(iNumber==g_pValues[i]) { i++; } iCount = i;g_iMaxCount = iCount; g_iMaxNumber = g_pValues[0]; iNumber = g_pValues[i]; while(i<g_uiArrayLength) { i+=iCount; iCurrCount+=iCount;iCountLeft = 0; if(i>=g_uiArrayLength-1) { int iDiff = i - g_uiArrayLength-1; i=g_uiArrayLength-1; if(iNumber==g_pValues[g_uiArrayLength-1]) { iCurrCount = iCurrCount + 1 - iDiff; if(g_iMaxCount<iCurrCount) { g_iMaxCount = iCurrCount; g_iMaxNumber = g_pValues[i]; } break; } while(iNumber!=g_pValues[i-1]) { iCountLeft++; i--; } iCurrCount = iCurrCount - iCountLeft - iDiff; if(g_iMaxCount<iCurrCount) { g_iMaxCount = iCurrCount; g_iMaxNumber = g_pValues[i-1]; } break; } else if(iNumber!=g_pValues[i]) { while(iNumber!=g_pValues[i-1]) { iCountLeft++; i--; } iCurrCount-=iCountLeft; iNumber = g_pValues[i]; if(g_iMaxCount<iCurrCount) { g_iMaxCount = iCurrCount; g_iMaxNumber = g_pValues[i-1]; iCount = iCurrCount; } iCurrCount = 0; } } } |

Let us know if you have any better idea to solve this algorithm. You can post your solution in the comments below.