#include <stdio.h>
/*
* Given a series of positive sequential numbers (incremented by 1), find the first missing number.
*/
/*
GetMissingNumber takes array and size of array as arguments
*/
// one approach
int GetMissingNumber1 (int a[], int n)
{
int i, total;
total = (n+1)*(n+2)/2;
for ( i = 0; i< n; i++)
total -= a[i];
return total;
}
// another approach
int GetMissingNumber2 (int a[], int n)
{
int i, num = a[0];
for (i=0; i<n; i++) {
if (num == a[i]) {
num++;
} else {
return num;
}
}
}
// try to write an implementation with O(log(n))
int missingNumber(int a[], int min, int max) {
int pivot;
if (min >= max)
return min + 1;
pivot = (min + max) / 2;
if (a[pivot] == pivot + 1)
return missingNumber(a, pivot + 1, max);
return missingNumber(a, min, pivot);
}
int GetMissingNumber3 (int a[], int n) {
return missingNumber(a, 0, n);
}
/*
* Program to test above functions
*/
int seq_main()
{
int a[] = {1,2,4,5,6};
int miss;
miss = GetMissingNumber1(a,5);
printf("%d\n", miss);
miss = GetMissingNumber2(a,5);
printf("%d\n", miss);
miss = GetMissingNumber3(a,5);
printf("%d\n", miss);
}
/*
* Output will be 3.
*/
/*
* Remove duplicates from a single linked list
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
struct _node *next;
int data;
}node;
typedef struct _SLL {
node *first;
int count;
}SLL;
static SLL *init_sll_fn()
{
SLL *head;
head = (SLL *)malloc(sizeof(SLL));
if (head == NULL) {
printf("Failed to initialize linked list\n");
return NULL;
}
head->first = NULL;
head->count = 0;
return head;
}
//below two functions are needed to insert and nodes into linked list
static int insert_sll_node_fn(SLL *head, int data)
{
node *n;
if (head == NULL) {
return -1;
}
n = (node *)malloc(sizeof(node));
if (n == NULL) {
return -1;
}
n->data = data;
n->next = head->first;
head->first = n;
head->count++;
return 0;
}
// this is the main function to delete duplicate nodes in single linked list
static void remove_duplicates_fn(SLL *head)
{
node *n, *nn;
node *p;
if (head == NULL) {
return;
}
n = head->first;
while(n != NULL) {
nn = n->next;
p = n;
while(nn != NULL) {
if (n->data == nn->data) {
p->next = nn->next; // update n->next
free(nn);
head->count--;
nn = p->next; // nn is the new n->next
} else {
p = nn;
nn = nn->next;
}
}
n = n->next;
}
return;
}
static void print_SLL(SLL *head) {
node *n;
if (head == NULL) {
return;
}
n = head->first;
while(n != NULL) {
printf("%d ", n->data);
n = n->next;
}
printf("[%d]\n", head->count);
}
int main()
{
SLL *ll;
int i;
int arr[]={1, 4, 2, 9, 8, 100, 3, 4, 2, 1};
ll = init_sll_fn();
for (i=0; i<10; i++) {
insert_sll_node_fn(ll, arr[i]);
}
print_SLL(ll);
remove_duplicates_fn(ll);
print_SLL(ll);
return 0;
}
