Best Method to find the missing interger in a array of contiguous positive integers.

If we have a array 10 intergers, that contains all integers from 1 to 10 except for one interger which is zero, then what is the best method to find the missing number.

Eg arr[10] = { 1, 2, 3, 4, 5, 0, 7, 8, 9, 10}

Answer:
The sum of n contiguous integers is (n* (n + 1) ) / 2.
The sum of 10 contiguous integers is (10 * 11) / 2 = 55.
The actual sum of integers in arr = 1+2+3+4+5+0+7+8+9+10 = 49.
The missing number is 55 - 49 = 6.

This method is easier when compared to setting the bit position for each number and then checking which bit is not set.

Complexity: SIMPLE.

Finding the middle of a single linked list

Node* MidOfLLUsing2Ptrs(Node *head)
{
Node* OneHop;
Node* TwoHop;
//If no node return NULL
if(head == NULL)
return NULL;
//If only one node then that is the middle
if(head->next == NULL)
return head;
OneHop = head;
TwoHop = OneHop->next;
while((TwoHop != NULL)&&(TwoHop->next != NULL))
{
OneHop = OneHop->next;
TwoHop = TwoHop->next->next;
}
return OneHop;
}


Calling the function:
Node *MidOne = MidOfLLUsing2Ptrs(head);


Complexity: SIMPLE.

Reversing a single linked list recursively

#include <stdio.h>
#include "malloc.h"

struct Node
{
struct Node * next;
int num;
};

void insertIntoLL(struct Node **head, int inum)
{
struct Node* temp;
temp = *head;
if(temp == NULL)
{
temp = (struct Node *) malloc(sizeof(Node));
temp->num = inum;
temp->next = NULL;
*head = temp;
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (struct Node *) malloc(sizeof(Node));
temp->next->num = inum;
temp->next->next = NULL;
}
}

void DisplayLL(struct Node* head)
{
Node* temp = head;
int num = 1;
while(temp != NULL)
{
printf("The value at node %d is %d\n", num, temp->num);
num++;
temp = temp->next;
}
}

Node* ReverseLLRecursively(Node* head)
{
Node *temp;
if(head->next)
{
temp=ReverseLLRecursively(head->next);
head->next->next=head;
head->next=NULL;
}
else
temp=head;
return temp;
}

int _tmain(int argc, _TCHAR* argv[])
{
Node *head = NULL;
insertIntoLL(&head,10);
insertIntoLL(&head,20);
insertIntoLL(&head,30);
insertIntoLL(&head,40);
insertIntoLL(&head,50);
DisplayLL(head);
Node *revHead = ReverseLLRecursively(head);
DisplayLL(revHead);
DisplayLL(head);
return 0;
}


Complexity: SIMPLE.

Print the contents of a Single Linked List in reverse order without using temporary pointer

#include "stdafx.h"
#include "malloc.h"

struct Node
{
struct Node * next;
int num;
};

void insertIntoLL(struct Node **head, int inum)
{
struct Node* temp;
temp = *head;
if(temp == NULL)
{
temp = (struct Node *) malloc(sizeof(Node));
temp->num = inum;
temp->next = NULL;
*head = temp;
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (struct Node *) malloc(sizeof(Node));
temp->next->num = inum;
temp->next->next = NULL;
}
}

void DisplayLL(struct Node* head)
{
Node* temp = head;
int num = 1;
while(temp != NULL)
{
printf("The value at node %d is %d\n", num, temp->num);
num++;
temp = temp->next;
}
}

void PrintReverse(int num, struct Node* head)
{
struct Node * temp = head;
if(temp->next != NULL)
{
num++;
PrintReverse(num, temp->next);
}
else
{
num++;
}
printf("The value at node %d is %d\n", num, temp->num);
}

int _tmain(int argc, _TCHAR* argv[])
{
Node *head = NULL;
insertIntoLL(&head,10);
insertIntoLL(&head,20);
insertIntoLL(&head,30);
insertIntoLL(&head,40);
insertIntoLL(&head,50);
DisplayLL(head);
PrintReverse(0,head);
return 0;
}


Complexity: SIMPLE.

Deleting last but one node in Single Linked List

void DeleteLastButOneNode(Node ** head)
{
Node * temp = *head;
while(temp->next->next != NULL)
temp = temp->next;
temp->num = temp->next->num;
free (temp->next);
temp->next = NULL;
}


Complexity: SIMPLE.

Finding the loop in Single Linked List

#include <stdio.h>
#include "malloc.h"


struct Node
{
struct Node * next;
int num;
};


void insertIntoLL(struct Node **head, int inum)
{
struct Node* temp;
temp = *head;
if(temp == NULL)
{
temp = (struct Node *) malloc(sizeof(Node));
temp->num = inum;
temp->next = NULL;
*head = temp;
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (struct Node *) malloc(sizeof(Node));
temp->next->num = inum;
temp->next->next = NULL;
}

}
Node* GetNodeAddress(int num, struct Node* head)
{
Node *temp = head;
if(temp->num == num)
return temp;
else
while(temp->next != NULL)
{
if(temp->num == num)
return temp;
temp = temp->next;
}
if(temp->num == num)
return temp;
else
return NULL;
}

void CheckLoopInLL(Node* head)
{
Node * slowGuy = head;
Node * fastGuy = head;
Node *fasterGuy = head;
while(slowGuy != NULL && fastGuy != NULL && fasterGuy != NULL)
{
slowGuy = slowGuy->next;
fastGuy = fastGuy->next->next;
fasterGuy = fasterGuy->next->next->next;
if((slowGuy == fastGuy)(slowGuy == fasterGuy)(fastGuy == fasterGuy))
{
printf("There is a loop");
break;
}

}
}

int _tmain(int argc, _TCHAR* argv[])
{
Node *head = NULL;
insertIntoLL(&head,10);
insertIntoLL(&head,20);
insertIntoLL(&head,30);
insertIntoLL(&head,40);
insertIntoLL(&head,50);
insertIntoLL(&head,60);
insertIntoLL(&head,70);
insertIntoLL(&head,80);
insertIntoLL(&head,90);
insertIntoLL(&head,100);
insertIntoLL(&head,110);
insertIntoLL(&head,120);
insertIntoLL(&head,130);
insertIntoLL(&head,140);
insertIntoLL(&head,150);
insertIntoLL(&head,160);
insertIntoLL(&head,170);
Node* node30 = GetNodeAddress(30,head);
Node* node170 = GetNodeAddress(170,head);
node170->next = node30;
CheckLoopInLL(head);
return 0;
}

Complexity: SIMPLE.

Size of Empty class

CONCEPT:
Object has a unique state, behaviour and identity.

class Empty { };
The size of an object of empty class is one byte.
If was zero then array of 100 object would all be pointing to the same memory location.

Complexity: SIMPLE.

Swapping 2 numbers without using one more variable

int a = 7;
int b = 8;
b = a + b; // 7 + 8 = 15
a = b - a; // 15 - 7 = 8
b = b - a; // 15 - 8 = 7

It can be used for other basic datatypes like char, double, float, long.
This solution however has the problem of overflow/underflow, so does

a = a * b;
b = a / b;
a = a / b;

For variables of same size XORing provides better solution.
a = a ^ b;
b = a ^ b;
a = a ^ b;


Complexity: SIMPLE.

Multipling a number by 7 without using * or + operator.

iNumIntoSeven = iNum <<3 ; //Equivalent to multiplying by 8.
iNumIntoSeven = iNumIntoSeven - iNum;

Complexity: SIMPLE.

Making a class Non Derivable in C++

CONCEPT USED:
Private members can be accessed only from within the class or by the friend of the class.

CODE SNIPPET:
class Usable;

class Usable_lock {
friend class Usable;
private:
Usable_lock() {}
Usable_lock(const Usable_lock&) {}
};

class Usable : public virtual Usable_lock {
public:
Usable();
Usable(char*);
// ...
};

Usable a;

class DD : public Usable { };

DD dd; // error: DD::DD() cannot access
// Usable_lock::Usable_lock(): private member

Complexity: INTERMEDIATE.

x+(~x+1)

#include <stdio.h>

void main(void){

int x = 100;
printf("%d",(x+(~x+1)));

}


Answer:
(~x+1) == one's compliment + 1 == two's compliment of x.
The sum of any number and it's 2's compliment is zero.

Complexity: INTERMEDIATE.