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, March 20, 2013

Find a missing number in sorted number list

 March 20, 2013     Programming problems in CPP     No comments   

You are given a sorted number list from 0 to n. The list is missing one number, find out that number

Approach:

We can run a binary search. Check the value in the middle, and see if the index of it is same as the value. If it is not, then 0 to mid range has a missing number, search in that range. Otherwise search in the range mid+1 to n. Continue similarly reducing the range by half every time, until you find the missing number.

#include <iostream>

using namespace std;

int findMissing(int *input, int len)
{
    int start = 0, end = len;
    while (start < len) {
        int mid = (start+end)/2;
        if (input[mid] == mid ) {
            if (input[mid+1] != mid+1) return mid+1;
            start = mid+1;
        } else {
            if (input[mid-1] != mid-1) return mid-1;
            end = mid;
        }
    }
    return -1;
}

const int MAX_LEN = 15;

int main()
{
    int input[MAX_LEN] = {0,1,2,3,4,5,6,7,8,9,10,12,13,14,15};
    cout << "Missing number: " <<  findMissing(input,MAX_LEN) << endl;
    return 0;
}
Output:-
Missing number: 11
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

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

Popular Posts

  • 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...
  • 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...
  • 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 ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • 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...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk