Paytm Question: Coin change problem

Problem: Find the number of ways of making changes for a given amount of Rupees/Cents etc.

Solution: Following are the steps to achieve the desired result -

1. Construct a table of size value + 1 where table[i] will tell the number of changes available using given coins.
2. Base case is 0 where table[0] = 1 as there is only one way to get the change of 0 i.e. leaving all coins.
3. Fill the table in bottom up manner by picking all coins one by one and update the table[j] where coins[i] <= j <= value.
4. table[n] contains the desired result.

Implementation:

int countChange(int coins[], int numOfCoins, int value)

{

int *table = new int[value + 1];

table[0] = 1;

for(int i = 1; i <= value; ++i)

table[i] = 0;

for(int i = 0; i < numOfCoins; ++i)

{

for(int j = coins[i]; j <= value; ++j)

table[j] += table[j - coins[i]];

}

return table[value];

}

Complexity: O(mn)

Paytm Question: Minimum distance between two numbers in an array

Problem: Given an unsorted array and two numbers num1 and num2, find the minimum distance between num1 and num2 in the given array.

Solution:

1. Traverse array from start and once either num1 or num2 are found, store the index of this occurrrence in a variable prevIndex.
2. Going ahead if the number at current index matches with either num1 or num2 then check if it is different from element at prevIndex. If yes, then update the minimum distance if needed. Make prevIndex = current index.

Implementation:

int minDistance(int arr[], int len, int num1, int num2)

{

int minDist = INT_MAX;

int prevIndex = -1;

for(int i = 0; i < len; ++i)

{

if(arr[i] == num1 || arr[i] == num2)

{

if(prevIndex == -1)

prevIndex = i;

else

{

if(arr[i] != arr[prevIndex] && (i - prevIndex) < minDist)

minDist = i - prevIndex;

prevIndex = i;

}

}

}

return minDist;

}

Complexity: O(n)