Cipher 3.2

The second installment of our coding competition ended recently. And as before the algorithms for the given problems are listed below. Although the difficulty of cipher 3.2 was comparatively less than that of cipher 3.1 and a lot of our contestants were successful in solving all of the given problems , we still hope that our solutions can be of help to you.

PROBLEM 1: INSERT A NODE AT THE HEAD OF A LINKED LIST

Given a pointer to the head of a linked list, insert a new node before the head. The Next value in the new node should point to Head and the Data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty.

SOLUTION:

1. Start.
2. Make a pointer , say P ,of the structure that the program is using.
3. Insert the Data of P.
4. P->Next=Head.
5. Head=P.
6. End.

PROBLEM 2:

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything.

SOLUTION:

1. Start.

We will first reverse the linked list.

2. Declare pointers P, Q and R of the structure.

3. Initialize P=Head , Q= NULL.

4. R=Q , Q=P ,P=P->Next, Q->Next=R.

5. Repeat step 4 till P!= NULL.

6. Head=Q.

We will now display the reversed Linked List.

7. Declare a pointer Temp of the given structure.

8. Temp=Head.

9. Print the Data at Temp. Temp=Temp-> Next.

10. Repeat Step 9 till Temp->Next!=NULL.

11. End.

PROBLEM 3:

Alexa has two stacks of non-negative integers, stack A=[a0,a1,….,a(n)] and stack B=[b0,b1…..,b(n)] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game:

• In each move, Nick can remove one integer from the top of either stack A or stack B .
• Nick keeps a running sum of the integers he removes from the two stacks.
• Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer given at the beginning of the game.
• Nick’s final score is the total number of integers he has removed from the two stacks.
• Given A,B and x for g games, find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified) during each game and print it on a new line.

SOLUTION:

1. Start.
2. Declare int TOP(A)= length of stack A and int TOP(B)=length of stack B.
3. Declare an int SUM=0 and Flag=0.
4. POP the topmost element of stack A and TOP(A)=TOP(A)-1. SUM=SUM+ element we popped. Flag=Flag+1.
5. POP the topmost element of stack B and TOP(B)=TOP(B)-1. SUM=SUM+ element we popped. Flag=Flag+1.
6. Continue Steps 4 and 5 till SUM=x.
7. Print Flag.
8. End.

PROBLEM 4:

There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies.

You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plant with more pesticide content than the plant to its left.

SOLUTION:

1. Start.
2. Declare an int array Check and an integer Flag.
3. Compare P[i] to P[i+1]. If P[i]< P[i+1], put P[i] in array Check.
4. Else continue .
5. Do steps 3 and 4 till the end of array P is reached.
6. If Check is an empty array , go to Step 9.
7. Else , equate P to Check ,make Check an empty array and Flag=Flag+1.
8. Repeat steps 2 to 7 , till Check is an empty array.
9. Print Flag.
10. Stop.

We hope that these solutions will help you come up with optimized solutions and clear your doubts if any.

-Shreya Mandal on behalf of Team Loop