Next Greater Element

Next Greater Element

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Solution:

1) Push the first element to stack.
2) Pick rest of the elements one by one and follow following steps in loop.
....a) Mark the current element as next.
....b) If stack is not empty, then pop an element from stack and compare it with next.
....c) If next is greater than the popped element, then next is the next greater element fot the popped element.
....d) Keep poppoing from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
....g) If next is smaller than the popped element, then push the popped element back.
3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.

void printNGE(int arr[], int n)

{

int i = 0;

struct stack s;

s.top = -1;

int element, next;

/* push the first element to stack */

push(&s, arr[0]);

// iterate for rest of the elements

for (i=1; i

{

next = arr[i];

if (isEmpty(&s) == false)

{

// if stack is not empty, then pop an element from stack

element = pop(&s);

/* If the popped element is smaller than next, then

a) print the pair

b) keep popping while elements are smaller and

stack is not empty */

while (element < next)

{

printf("\n %d --> %d", element, next);

if(isEmpty(&s) == true)

break;

element = pop(&s);

}

/* If element is greater than next, then push

the element back */

if (element > next)

push(&s, element);

}

/* push next to stack so that we can find

next greater for it */

push(&s, next);

}

/* After iterating over the loop, the remaining

elements in stack do not have the next greater

element, so print -1 for them */

while(isEmpty(&s) == false)

{

element = pop(&s);

next = -1;

printf("\n %d --> %d", element, next);

}

}

* Find duplicates in O(n) time and O(1) extra space

/*Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.*/

#include "stdio.h"

#include"stdlib.h"
void printRepeating(int arr[], int size)
{
int i,index=0;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++)
{
index=abs(arr[i])%size;
if(arr[index] == 0)
arr[index]=-size;
else if(arr[index]>0 && arr[index]<size)
arr[index] = -arr[index];
else if(arr[index]<0)
{
printf(" %d ", abs(arr[i]));
arr[index]=-arr[index];
arr[index]+=size;
}
}
//restore previous array
for(i=0;i <size;i++)
arr[i]=abs(arr[i])%size;
}

int main()
{
int arr[] = {1, 1,1,1,1,1,2,2,3,0,0,0};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Write a C program to sort a stack in ascending order without using extra space

Write a C program to sort a stack in ascending order. You should not
make any assumptions about how the stack is implemented. The following
are the only
functions that should be used to write this program:
Push | Pop | Top | IsEmpty | IsFull
Method 1: Recursion

void sort(stack)
{
type x;

if (!isEmpty(stack)) {
x = pop(stack);
sort(stack);
insert(x, stack);
}
}

void insert(x, stack)
{
type y;

if (!isEmpty(stack) && top(stack) .<. x) y = pop(stack);
insert(x, stack);
push(y, stack);
} else {
push(x, stack);
}
}


Method:2 Iterative use one more stack
void sort_stack(Stack * src, Stack * dest)
{
while (!src->IsEmpty())
{
Int tmp = src->Pop();
while(!dest->IsEmpty() && dest->Top() > tmp)
{
src->Push(dest->Pop());
}
dest->Push(tmp);
}


Methode 3:
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i .<. top){
ascending(s, top);
push(i);
}
else{
ascending(s, i);
push(top);
}

}

What do lvalue and rvalue mean?

What do lvalue and rvalue mean?
An lvalue is an expression that could appear on the left-hand sign of an assignment (An object that has a location). An rvalue is any
expression that has a value (and that can appear on the right-hand sign of an assignment).
The lvalue refers to the left-hand side of an assignment expression. It must always evaluate to a memory location. The rvalue represents the
right-hand side of an assignment expression; it may have any meaningful combination of variables and constants.
Is an array an expression to which we can assign a value?
An lvalue was defined as an expression to which a value can be assigned. The answer to this question is no, because an array is composed
of several separate array elements that cannot be treated as a whole for assignment purposes.
The following statement is therefore illegal:
int x[5], y[5];
x = y;
Additionally, you might want to copy the whole array all at once. You can do so using a library function such as the memcpy() function, which
is shown here:
memcpy(x, y, sizeof(y));
It should be noted here that unlike arrays, structures can be treated as lvalues. Thus, you can assign one
structure variable to another structure variable of the same type, such as this:
typedef struct t_name
{
char last_name[25];
char first_name[15];
char middle_init[2];
} NAME;
...
NAME my_name, your_name;
...
your_name = my_name;

Whats wrong with the expression a[i]=i++; ? Whats a sequence point?

Whats wrong with the expression a[i]=i++; ? Whats a sequence point?
Although its surprising that an expression like i=i+1; is completely valid, something like a[i]=i++; is not. This is because all accesses to an
element must be to change the value of that variable. In the statement a[i]=i++; , the access to i is not for itself, but for a[i] and so its
invalid. On similar lines, i=i++; or i=++i; are invalid. If you want to increment the value of i, use i=i+1; or i+=1; or i++; or ++i; and not some
combination.
A sequence point is a state in time (just after the evaluation of a full expression, or at the ||, &&, ?:, or comma operators, or just before a
call to a function) at which there are no side effects.
The ANSI/ISO C Standard states that
Between the previous and next sequence point an object shall have its stored
value modified at most once by the evaluation of an expression. Furthermore,
the prior value shall be accessed only to determine the value to be stored.
At each sequence point, the side effects of all previous expressions will be completed. This is why you cannot rely on expressions such as
a[i] = i++;, because there is no sequence point specified for the assignment, increment or index operators, you don't know when the effect
of the increment on i occurs.
The sequence points laid down in the Standard are the following:

1.The point of calling a function, after evaluating its arguments.
2.The end of the first operand of the && operator.
3.The end of the first operand of the || operator.
4.The end of the first operand of the ?: conditional operator.
5.The end of the each operand of the comma operator.
6.Completing the evaluation of a full expression. They are the following:
1-Evaluating the initializer of an auto object.
2-The expression in an ?ordinary? statement?an expression followed by semicolon.
3-The controlling expressions in do, while, if, switch or for statements.
4-The other two expressions in a for statement.
5-The expression in a return statement.

Segmentation fault, access violation, core dump and Bus error

What do Segmentation fault, access violation, core dump and Bus error mean?
The segmentation fault, core dump, bus error kind of errors usually mean that the program tried to access memory it shouldn't have.
Probable causes are overflow of local arrays; improper use of null pointers; corruption of the malloc() data structures; mismatched function
arguments (specially variable argument functions like sprintf(), fprintf(), scanf(), printf()).
For example, the following code is a sure shot way of inviting a segmentation fault in your program:
sprintf(buffer,"%s %d","Hello");
So whats the difference between a bus error and a segmentation fault?
A bus error is a fatal failure in the execution of a machine language instruction resulting from the processor
detecting an anomalous condition on its bus.
Such conditions include:
-
-
-
-
-
Invalid address alignment (accessing a multi-byte number at an odd address).
Accessing a memory location outside its address space.
Accessing a physical address that does not correspond to any device.
Out-of-bounds array references.
References through uninitialized or mangled pointers.
A bus error triggers a processor-level exception, which Unix translates into a "SIGBUS" signal,which if not caught, will terminate the current
process. It looks like a SIGSEGV, but the difference between the two is that SIGSEGV indicates an invalid access to valid
memory, while SIGBUS indicates an access to an invalid address.
Bus errors mean different thing on different machines. On systems such as Sparcs a bus error occurs when you access memory that is not
positioned correctly.
Maybe an example will help to understand how a bus error occurs
#include " stdlib.h"
#include " stdio.h"
int main(void)
{
char *c;
long int *i;
c = (char *) malloc(sizeof(char));
c++;
i = (long int *)c;
printf("%ld", *i);
return 0;
}
On Sparc machines long ints have to be at addresses that are multiples of four (because they are four bytes long), while chars do not (they
are only one byte long so they can be put anywhere). The example code uses the char to create an invalid address, and assigns the long int
to the invalid address. This causes a bus error when the long int is dereferenced.
A segfault occurs when a process tries to access memory that it is not allowed to, such as the memory at address 0 (where NULL usually
points). It is easy to get a segfault, such as the following example, which dereferences NULL.
#include " stdio.h"
int main(void)
{
char *p;
p = NULL;
putchar(*p);
return 0;
}

Write a C program to implement a Generic Linked List

Write a C program to implement a Generic Linked List.
Here is a C program which implements a generic linked list. This is also one of the very popular interview questions thrown around. The
crux of the solution is to use the void C pointer to make it generic. Also notice how we use function pointers to pass the address of
different functions to print the different generic data.

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct list {
void *data;
struct list *next;
} List;
struct check {
int i;
char c;
double d;
} chk[] = { { 1, 'a', 1.1 },
{ 2, 'b', 2.2 },
{ 3, 'c', 3.3 } };

void insert(List **, void *, unsigned int);
void print(List *, void (*)(void *));
void printstr(void *);
void printint(void *);
void printchar(void *);
void printcomp(void *);
List *list1, *list2, *list3, *list4;
int main(void)
{
char c[]
= { 'a', 'b', 'c', 'd' };
int i[]
= { 1, 2, 3, 4 };
char *str[] = { "hello1", "hello2", "hello3", "hello4" };
list1 = list2 = list3 = list4 = NULL;
insert(&list1, &c[0], sizeof(char));
insert(&list1, &c[1], sizeof(char));
insert(&list1, &c[2], sizeof(char));
insert(&list1, &c[3], sizeof(char));
insert(&list2, &i[0], sizeof(int));
insert(&list2, &i[1], sizeof(int));
insert(&list2, &i[2], sizeof(int));
insert(&list2, &i[3], sizeof(int));
insert(&list3,str[0],strlen(str[0])+1);
insert(&list3,str[1],strlen(str[0])+1);
insert(&list3,str[2],strlen(str[0])+1);
insert(&list3,str[3],strlen(str[0])+1);
insert(&list4, &chk[0], sizeof chk[0]);
insert(&list4, &chk[1], sizeof chk[1]);
insert(&list4, &chk[2], sizeof chk[2]);
printf("Printing characters:");
print(list1, printchar);
printf(" : done\n\n");
printf("Printing integers:");
print(list2, printint);
printf(" : done\n\n");
printf("Printing strings:");
print(list3, printstr);
printf(" : done\n\n");
printf("Printing composite:");
print(list4, printcomp);
printf(" : done\n");
return 0;
}
void insert(List **p, void *data, unsigned int n)
{
List *temp;
int i;
/* Error check is ignored */
temp = malloc(sizeof(List));
temp->data = malloc(n);
for (i = 0; i <>
*(char *)(temp->data + i) = *(char *)(data + i);
temp->next = *p;
*p = temp;
}
void print(List *p, void (*f)(void *))
{
while (p)
{
(*f)(p->data);
p = p->next;
}
}
void printstr(void *str)
{
printf(" \"%s\"", (char *)str);
}
void printint(void *n)
{
printf(" %d", *(int *)n);
}
void printchar(void *c)
{
printf(" %c", *(char *)c);
}
void printcomp(void *comp)
{
struct check temp = *(struct check *)comp;
printf(" '%d:%c:%f", temp.i, temp.c, temp.d);
}

REVERSE A Doubly LinkList

#include"stdio.h'
#include'ctype.h"
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
mynode *head, *tail;
void add_node(int value);
void print_list();
void reverse();
int main()
{
head=NULL;
tail=NULL;
add_node(1);
add_node(2);
add_node(3);
add_node(4);
add_node(5);
print_list();
reverse();
print_list();
return(1);
}
void add_node(int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(head == NULL)
{
printf("\nAdding a head pointer\n");
head=temp;
tail=temp;
temp->value=value;
}
else
{
for(cur=head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
tail=temp;
}
}
void print_list()
{
mynode *temp;
printf("\n--------------------------------\n");
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("\n[%d]\n",temp->value);
}
}
void reverse()
{
mynode *cur, *temp, *save_next;
if(head==tail)return;
if(head==NULL || tail==NULL)return;
for(cur=head;cur!=NULL;)
{
printf("\ncur->value : [%d]\n",cur->value);
temp=cur->next;
save_next=cur->next;
cur->next=cur->prev;
cur->prev=temp;
cur=save_next;
}
temp=head;
head=tail;
tail=temp;
}

Reverse string by words in c

That is, given a sentence like this


Sachin is a good boy


The in place reverse would be


boy good a is Sachin

Method1

First reverse the whole string and then individually reverse the words


Sachin is a good boy
<------------->

yob doog a si nihcaS
<-> <--> <-> <-> <->

boy good a is Sachin



Here is some C code to do the same ....


/*
Algorithm..

1. Reverse whole sentence first.
2. Reverse each word individually.

All the reversing happens in-place.
*/

#include

void rev(char *l, char *r);


int main(int argc, char *argv[])
{
char buf[] = "the world will go on forever";
char *end, *x, *y;

// Reverse the whole sentence first..
for(end=buf; *end; end++);
rev(buf,end-1);


// Now swap each word within sentence...
x = buf-1;
y = buf;

while(x++ <>
{
if(*x == '\0' || *x == ' ')
{
rev(y,x-1);
y = x+1;
}
}

// Now print the final string....
printf("%s\n",buf);

return(0);
}


// Function to reverse a string in place...
void rev(char *l,char *r)
{
char t;
while(l <>
{
t = *l;
*l++ = *r;
*r-- = t;
}
}

Method2

Another way to do it is, allocate as much memory as the input for the final output. Start from the right of the string and copy the words one by one to the output.


Input : I am a good boy
< --
< -------
< ---------
< ------------
< --------------


Output : boy
: boy good
: boy good a
: boy good a am
: boy good a am I


The only problem to this solution is the extra space required for the output and one has to write this code really well as we are traversing the string in the reverse direction and there is no null at the start of the string to know we have reached the start of the string!. One can use the strtok() function to breakup the string into multiple words and rearrange them in the reverse order later.

Method3

Create a linked list like



| I | -> | <> | -> | am | -> | <> | -> | a | -> | <> | -> | good | -> | <> | -> | boy | -> | NULL |



Now its a simple question of reversing the linked list!. There are plenty of algorithms to reverse a linked list easily. This also keeps track of the number of spaces between the words. Note that the linked list algorithm, though inefficient, handles multiple spaces between the words really well.

#include "stdio"
#include "stdlib"

#include "string"

/* reverse a string in place, return str */
static char* reverse(char* str)
{
char* left = str;
char* right = left + strlen(str) - 1;
char tmp;
while (left < style="color: rgb(0, 51, 0);"> tmp = *left;
*left++ = *right;
*right-- = tmp;
}
return str;
}

static int reverseWords(
const char* instr, /* in: string of words */
char* outstr) /* out: reversed words */
/* (caller must ensure big enough) */
{int k;
char* p;
char* buf;
*outstr = '\0';
if ((buf = (char*)malloc(strlen(instr)+1)) == NULL) {
fprintf(stderr, "oops, out of memory\n");
return -1;
}
strcpy(buf, instr);
reverse(buf);
if ((p = strtok(buf, " \t")) == NULL) {
free(buf);
return 0;
}

strcpy(outstr, reverse(p));
outstr += strlen(p);
while ((p = strtok(NULL, " \t")) != NULL) {
*outstr++ = ' ';

strcpy(outstr, reverse(p));
outstr += strlen(p);
}
free(buf);
return 0;
}

int main()
{
char instr[256];
char outstr[256];
printf("\n enter a string:");
gets(instr);
reverseWords(instr, outstr);
printf("in='%s' out='%s'\n", instr, outstr);
return 0;
}





:::::::::::::::::::::::::::::::::::::::
#include"stdio.h"

/* function prototype for utility function to
reverse a string from begin to end */
void reverse(char *begin, char *end);

/*Function to reverse words*/
void reverseWords(char *s)
{
char *word_begin = s;
char *temp = s; /* temp is for word boundry */

/*STEP 1 of the above algorithm */
while( *temp )
{
temp++;
if (*temp == '\0')
{
reverse(word_begin, temp-1);
}
else if(*temp == ' ')
{
reverse(word_begin, temp-1);
word_begin = temp+1;
}
} /* End of while */

/*STEP 2 of the above algorithm */
reverse(s, temp-1);
}

/* UTILITY FUNCTIONS */
/*Function to reverse any sequence starting with pointer
begin and ending with pointer end */
void reverse(char *begin, char *end)
{
char temp;
while (begin < end )
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}

/* Driver function to test above functions */
int main()
{
char s[] = "i like this program very much";
char *temp = s;
reverseWords(s);
printf("%s", s);
getchar();
return 0;
}

binary tree in c

A normal search across a BST (Binary Search Tree) would look like this

bool BinaryTree::Search (int data )
{
Node *current = this->root;

while ( current != NULL )
{
if (current->data < data)
{
current = current->left;
}
else if (current->data > data)
{
current = current->right;
}
else if ( current->data == data )
{
return true;
}
}

return false;
}

You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node. If you look at the number of statements, there is one conditional check on the while, and an average of 1.5 conditional checks inside the loop. That makes it a total of 2.5 checks every iteration. On a tree with a 1000 nodes, that’s 2500 checks.

Let’s see how we can improve this. I am using the sentinel node technique for this purpose. In this case static Node * Leaf;

This is how the search will look like

static Node* Leaf;

bool BinaryTree::Search (int data )
{
Node *current = this->root;

Leaf->data = data;

while ( current->data != lead->data )
{
if (current->data < data)
{
current = current->left;
}
else
{
current = current->right;
}
}

return (current != Leaf);
}
The sentinel is a static node, and while building the tree, you point all the leaf nodes to this sentinel node instead of NULL. Before you start the search, you set the value of the sentinel node to the data you are searching for. This way you are guaranteed to get a hit. You just need to do one extra check at the end to see if the Hit node was a Node in the tree or the sentinel node. If you look at the number of conditional statements in the loop, there is one in the while statement and one inside the loop, that makes it 2 searches every iteration. You just saved half a conditional statement. Don’t underestimate this improvement. E.g. In a 1000 iteration loop you saved 500 checks.

This is extremely useful with large trees or when you are searching the tree several times or any other scenario where this call happens in a hot section.

Reverse a single linked list using single pointer iteratively and recursively

(Recursive)
struct list * reverse_ll( struct list * head)
{
struct list * temp = NULL;

if ( head == NULL)
return NULL;
if ( head->next == NULL )
return head;

temp = reverse_ll ( head->next );
head->next -> next = head;
head->next = NULL;
return temp;
}

int main()
{
...
head = reverse_ll(head);
...
}
____________________________________________________________________
(Iterative)

#define pointer_swap( a, b) ((int)(a))^=((int)(b))^=((int)(a))^=((int)(b))

struct list * reverse_ll( struct list * head)
{
struct list * temp = NULL;
if (head && head->next) {
temp = head->next;
head->next = NULL;
} else {
return head;
}
while (temp->next) {
pointer_swap(head, temp->next);
pointer_swap(head,temp);
}
temp->next = head;
//head = temp;
return temp;
}
____________________________________________________________________



. Minimized version of my code.
#define pointer_swap(a,b) ((int)(a)) ^= ((int)(b)) ^= ((int)(a)) ^= ((int)(b))

struct list * reverse_ll(struct list * head)
{
struct list * temp = NULL;

while(head) {
pointer_swap(temp,head->next);
pointer_swap(temp,head);
}
return temp;
}

Find the two repeating elements in a given array

Find the two repeating elements in a given array June 9, 2010 You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers. For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5 The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2. Method 1 (Basic) Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop. This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements. view source print? #include #include void printRepeating(int arr[], int size) { int i, j; printf(" Repeating elements are "); for(i = 0; i <> for(j = i+1; j <> if(arr[i] == arr[j]) printf(" %d ", arr[i]); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } Time Complexity: O(n*n) Auxiliary Space: O(1) Method 2 (Use Count array) Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate. This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements. view source print? #include #include void printRepeating(int arr[], int size) { int *count = (int *)calloc(sizeof(int), (size - 2)); int i; printf(" Repeating elements are "); for(i = 0; i <> { if(count[arr[i]] == 1) printf(" %d ", arr[i]); else count[arr[i]]++; } } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } Time Complexity: O(n) Auxiliary Space: O(n) Method 3 (Make two equations) We have to find two numbers, so to unknowns. We know the sum of n numbers is n(n+1)/2 and product is n!. Make two equations using these sum and product formulas, and get values of two unknowns using the two equations. Let summation of all numbers in array be S and product be P Let the numbers which are being repeated are X and Y. X + Y = S – n(n+1)/2 XY = P/n! Using above two equations, we can find out X and Y. For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960. X + Y = 21 – 15 = 6 XY = 960/5! = 8 X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2 Using below two equations, we easily get X = (6 + 2)/2 and Y = (6-2)/2 X + Y = 6 X – Y = 2 Thanks to geek4u for suggesting this method. As pointed by Beginer , there can be addition and multiplication overflow problem with this approach. The methods 3 and 4 use all useful information given in the question view source print? #include #include #include /* function to get factorial of n */ int fact(int n); void printRepeating(int arr[], int size) { int S = 0; /* S is for sum of elements in arr[] */ int P = 1; /* P is for product of elements in arr[] */ int x, y; /* x and y are two repeating elements */ int D; /* D is for difference of x and y, i.e., x-y*/ int n = size - 2, i; /* Calculate Sum and Product of all elements in arr[] */ for(i = 0; i <> { S = S + arr[i]; P = P*arr[i]; } S = S - n*(n+1)/2; /* S is x + y now */ P = P/fact(n); /* P is x*y now */ D = sqrt(S*S - 4*P); /* D is x - y now */ x = (D + S)/2; y = (S - D)/2; printf("The two Repeating elements are %d & %d", x, y); } int fact(int n) { return (n == 0)? 1 : n*fact(n-1); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } Time Complexity: O(n) Auxiliary Space: O(1) Method 4 (Use XOR) Thanks to neophyte for suggesting this method. The approach used here is similar to method 2 of this post. Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y. The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y. view source print? void printRepeating(int arr[], int size) { int xor = arr[0]; /* Will hold xor of all elements */ int set_bit_no; /* Will have only single set bit of xor */ int i; int n = size - 2; int x = 0, y = 0; /* Get the xor of all elements in arr[] and {1, 2 .. n} */ for(i = 0; i <> xor ^= arr[i]; for(i = 1; i <= n; i++) xor ^= i; /* Get the rightmost set bit in set_bit_no */ set_bit_no = xor & ~(xor-1); /* Now divide elements in two sets by comparing rightmost set bit of xor with bit at same position in each element. */ for(i = 0; i <> { if(arr[i] & set_bit_no) x = x ^ arr[i]; /*XOR of first set in arr[] */ else y = y ^ arr[i]; /*XOR of second set in arr[] */ } for(i = 1; i <= n; i++) { if(i & set_bit_no) x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/ else y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */ } printf("\n The two repeating elements are %d & %d ", x, y); } int main() { int arr[] = {4, 2, 4, 5, 2, 3, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } Method 5 (Use array elements as index) Thanks to Manish K. Aasawat for suggesting this method. traverse the list for i= 1st to n+2 elements { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // i.e., A[abs(A[i])] is negative this element (ith element of list) is a repetition } Example: A[] = {1,1,2,3,2} i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ; so list now is {-1,1,2,3,2} i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition, now list is {-1,1,2,3,2} i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated now list becomes {-1,-1,-2,3,2} i=4 ; and A[4]=3 is not repeated i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition, This method modifies the original array. view source print? #include #include void printRepeating(int arr[], int size) { int i; printf("\n The repeating elements are"); for(i = 0; i <> { if(arr[abs(arr[i])] > 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else printf(" %d ", abs(arr[i])); } } int main() { int arr[] = {1, 3, 2, 2, 1}; int arr_size = sizeof(arr)/sizeof(arr[0]); printRepeating(arr, arr_size); getchar(); return 0; } The problem can be solved in linear time using other method also