#### 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.

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 from a given array of numbers

**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.