StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Wednesday, January 16, 2013

Find the smallest distance between given two numbers

 January 16, 2013     Programming problems in CPP     No comments   

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

  1. Have one input number as first and the other one as second

  2. Whenever you find the first, move last position to that position (initially start with some large negative number)

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

  4. 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
Email ThisBlogThis!Share to XShare to Facebook
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Python FastAPI file upload and download
    In this article, we will look at an example of how to implement a file upload and download API in a Python FastAPI microservice. Example bel...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Accessing the Kubernetes API
    In this article, we will explore the steps required to access the Kubernetes API and overcome common challenges. All operations and communic...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Scheduling jobs in Python
    When developing applications and microservices we run into scenarios where there is a need to run scheduled tasks. Examples include performi...
  • Using Tekton to deploy KNative services
    Tekton is a popular open-source framework for building continuous delivery pipelines. Tekton provides a declarative way to define pipelines ...

Copyright © StackStalk