A swap means removing any element from the array and appending it to the back of the same array. Given an array of integers find the minimum number of swaps needed to sort the array.
Example :
A[3]= 3 , 2 , 1
B[3]= 1, 2, 3
i=0 j=0
A[0]!=B[0]
So swap ++ ( Whenever you increment assume that A[i] is removed and appended at the end )
i++
Now i=1 j=0
A[1]!=B[0]
So swap++
i++
Now i=2 j=0
A[2]==B[0]
Now j++
i == n now and hence break the loop
No. of swaps = 2
Recursive codes are little complicated to code.But once we get an hang of it, it turns out to be easier than iterative code
[gist https://gist.github.com/vishnujayvel/7811534]Let initial flowers=x
dey get double up that is nw we get 2x
let y flowers be offered to GOD 1
remaining are 2x-y which doubled that is 4x-2y
again y flowers offered to GOD 2
remainin are 4x-3y which doubled again that is 8x-6y
again y flowers offered to GOD 3
remainin are 8x-7y which doubled again that is 16x-14y
again y flowers offered to GOD 4
remainin are 16x-15y
no flowers should b left after
therefore 16x-15y=0
–> x/y=15/16
so x=15 n y =16 atleast
15*2=30,16 offer to god1
14*2=28,16 offer to god2
12*2=24,16 offer to god3
8*2=16,16 offer to god4
0 left
Since we cannot use extra space, take advantage of the fact that the array has elements only from 1 to n
and there are n elements in the array(index ranges from 0 to n-1)
So if 1 occurs make value at 0th index negative
if 2 occurs make the value at 1st index negative
if n occurs make the value at n-1th index negative
So if the same number occurs again then the value at that number index will be found negative already and
voila !Thus we found a way finding repeating number.
Algorithm
traverse the list for i= 0 to n-1 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
}
| #include<iostream> | |
| using namespace std; | |
| struct node | |
| { | |
| int data; | |
| struct node *next; | |
| }; | |
| struct node* createNewNode(int data){ | |
| struct node* nn=new struct node(); | |
| nn->data=data; | |
| nn->next=NULL; | |
| return nn; | |
| } | |
| struct node* sortedInsert(node *head,int data){ | |
| struct node* newNode=createNewNode(data); | |
| struct node* current=head; | |
| if(current==NULL){//if the circular LL is empty | |
| newNode->next=newNode; | |
| head=newNode; | |
| } | |
| else if(current->data>=newNode->data){// if newNode has to be inserted before the head | |
| while(current->next!=head){ | |
| current=current->next; | |
| } | |
| current->next=newNode; | |
| newNode->next=head; | |
| head=newNode; | |
| } | |
| else{//if the newNode has to be inserted somewhere inbetween the list | |
| while(current->next!=head&¤t->next->data<newNode->data) | |
| current=current->next; | |
| newNode->next=current->next; | |
| current->next=newNode; | |
| } | |
| return head; | |
| } | |
| void printList(struct node *start) | |
| { | |
| struct node *temp; | |
| if(start != NULL) | |
| { | |
| temp = start; | |
| cout<<endl; | |
| do { | |
| cout<<temp->data<<" "; | |
| temp = temp->next; | |
| } while(temp != start); | |
| } | |
| } | |
| int main() | |
| { | |
| struct node *head = NULL; | |
| for(int i = 6; i>0; i--) | |
| { | |
| head=sortedInsert(head,i); | |
| } | |
| printList(head); | |
| return 0; | |
| } | |
Start two pointers i & j from the end of the string.
a. Keep copying the character from ith location to the jth location and decrement both i & j
b. When i encounters a space, decrement i, but not j
c Repeat steps a & b until i falls of the beginning of the string.
d. Keep setting ‘space’ character at jth location and decrement j unitl j falls of the beginning of the string
source:careercup.com
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:
Three flags should be used for pointing the last of 0, the last of 1, and the first of 2.
The unknown region is shrunk while maintaining these conditions
source: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
Provided n1->n2->n3->n4->n5
in general for each pair starting with n
have a temp variable that will keep copy of reference to n.next
Consider the link list n1->n2->n3->……
and n=n1
temp=n.next //temp=n2
n.next=n.next.next//n1.next=n1.next.next=n3
temp.next=n //n2.next=n1
Now move n to n.next//n=n1.next=n3
Repeat the same for next pair.but we have to link previous pair with the current pair
Which will have previous pairs 2nd element ? its temp.next
So make temp.next.next=n.next
Thats it!!
Also you can swap the pairs by just swapping the value.That is way too simple.Look at the 2nd function
Source code:
coding hangover 