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

Saturday, March 30, 2013

Missing and Duplicate numbers in a continuous list

 March 30, 2013     Programming problems in CPP     No comments   

Given a sorted array of continuous numbers, there is one number missing and another one occurring twice. Find the missing and duplicate.

Approach :- We iterate through the array. for each integer we check if the index is matching the number. There are 3 possible cases (when iterator is 3):
1. 0,1,2,3,4,5 continues
2. 0,1,2,4,5,6 found missing
3. 0,1,2,7,3,5 found duplicate

Note down if you found a missing or duplicate. If you found a missing, then next numbers are 1+. And if you found duplicate, next numbers are 1-. So we use delta to keep track of that when we continue to find the other entity. When we found both the entities we break the loop.

Solution:

#include <iostream>

using namespace std;

void findMissingAndDuplicate(int *input,int *missing, int *duplicate,int len)
{
int delta = 0;
bool foundMissing = false, foundDuplicate = false;

for(int i=0;i<len;i++) {
if(!foundMissing && (input[i] == i+delta+1)) {
*missing = i+delta;
delta += 1;
foundMissing =true;
if (foundDuplicate)
break;
} else if (!foundDuplicate && (input[i] != i+delta)) {
*duplicate = input[i];
foundDuplicate = true;
if (foundMissing)
break;
delta -= 1;
}
}
}

const int MAX_LEN = 16;

int main()
{
int input[MAX_LEN] = {0,1,2,3,4,5,3,6,7,8,9,10,12,13,14,15};
int missing, duplicate;
findMissingAndDuplicate(input,&missing, &duplicate,MAX_LEN);
cout << "Missing number: " << missing << " and duplicate: " << duplicate << endl;
return 0;
}
Output:-
Missing number: 11 and duplicate: 3

Other option is to first find only the missing number. Then do a summation of all the numbers and subtract the sum of numbers minus the missing number. Conversely, find the duplicate number first and then apply the sum trick to find out the missing.

Binary search is not possible. But a divide and conquer method can be applied, but it gets messier. Below is an attempt to do this (not complete code).

#include <iostream>

using namespace std;

// find a missing in the given range
void findMissing(int *input,int *missing, int start, int len)
{
}

// find a duplicate in the given range
bool findDuplicate(int *input,int *duplicate, int start, int len)
{
}

// For a given missing find the duplicate in the given range!
bool findDuplicateNormal(int *input,int *missing, int *duplicate, int start, int len)
{
}

// return: 0 - not found : 1 - miss found : 2 - duplicate found : 3 both found.
// values 1 and 2 become irrevalant as they never happen.
int findMissingAndDuplicate(int *input,int *missing, int *duplicate, int start, int len)
{
int mid = start + (len / 2);
if (input[mid] == mid) { // duplicate and miss are either in the first half - caseA
// duplicate and miss are either in the second half. caseB
// or miss in 2nd half and duplicate on both caseC
// neither miss nor duplicate caseD
int ret = findMissingAndDuplicate(input,missing, duplicate, start, len);
switch (ret) {
case 0: // none found --> caseB, caseC, caseD
findMiss(input,missing,mid,len/2);
bool retDupFound = findDuplicate(input,missing,mid,len/2);
if (!retDupFound) { // it is duplicate on both case! --> caseC
bool localDupFound = findDuplicateNormal(input, missing, duplicate, start, len);
if (!localDupFound) // caseD!
return 0;
}
return 3;
break;
case 1: // found missing. This should not occur!
break;
case 2: // found duplicate. This should not occur!
break;
case 3: // both are found --> caseA
return 3;
}
} else if (input[mid] < mid) { // duplicate in 1st half and miss in 2nd half
findDuplicate(input,duplicate,start, len/2);
findMiss(input,missing,mid,len/2);
return 3;
} else { // miss in 1st half and duplicate on both --> caseE
// miss in 1st half and duplicate in 2nd half --> caseF
findMiss(input, missing, mid, len/2);
int retDupFound = findDuplicate(input,duplicate,start, len/2);
if (!retDupFound) { // it is duplicate on both case! caseE
findDuplicateNormal(input, missing, duplicate, start, len);
}
return 3; // applicable for both caseE or caseF
}
return 0;
}

const int MAX_LEN = 16;

int main()
{
int input[MAX_LEN] = {0,1,2,3,4,5,3,6,7,8,9,10,12,13,14,15}; // duplicate in 1st half, miss in 2nd

int missing, duplicate;
findMissingAndDuplicate(input,&missing, &duplicate,MAX_LEN);
cout << "Missing number: " << missing << " and duplicate: " << duplicate << endl;
return 0;
}
  • 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