**Find the smallest distance between given two numbers in a stream of numbers with duplicates.**

For example: Given a stream of numbers, { 4, 3, 1, 1, 3, 4, 8, 2, 5, 6, 3, 1, 2, 7, 5}. For 2 and 3, the smallest distance is 1 that happens near the end.

The approach:-

- Have one input number as first and the other one as second
- Whenever you find the first, move last position to that position (initially start with some large negative number)
- If you hit a second number find the distance from the last position and see if it betters the previous known distance (initially set previous known distance to some large negative number). Update previous better distance if current is bettered. Also swap the first and second, so that we can check for the next distance that is going to happen.
- On hitting the end of the stream we have the minimum distance

The solution:-

#include <iostream>

using namespace std;

#define MAX 15

int main()

{

int array[MAX] = { 4, 3, 1, 1, 3, 4, 8, 2, 5, 6, 3, 1, 2, 7, 5 };

int firstNumber = 2;

int secondNumber = 3;

int minDistance = 9999; // some max.

int lastPosition = -minDistance;

cout << "The smallest distance between " << firstNumber << " and " << secondNumber << " is: " << endl;

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

{

if (array[i] == secondNumber)

{

if (minDistance > (i-lastPosition-1))

minDistance = i-lastPosition - 1;

int temp = secondNumber;

secondNumber = firstNumber;

firstNumber = temp;

lastPosition = i;

}

else if (array[i] == firstNumber)

{

lastPosition = i;

}

}

cout << minDistance << endl;

return 0;

}

Output:-

The smallest distance between 2 and 3 is:

1

## 0 comments:

## Post a Comment