Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Arrange the Salary

Last Updated on June 17, 2022 by Ria Pathak

### CONCEPTS USED:

Basic Pointer Manipulation

Medium

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a linked list of `N` elements and a value `X`, your task is to arrange the list in such a way that all elements less than `X` comes first, then finally all elements greater than or equal to `X`.

NOTE : You have to maintain the original relative order of the elements at the time of arranging the salary.

See original problem statement here

#### For Example:

``````Input :

list = 9 -> 6 -> 3 -> 7 -> 1 -> 4
K = 5

Output: 3 -> 1 -> 4 -> 9 -> 6 -> 7

Explaination : Elements smaller than 5 i.e. 3, 1, 4 are arranged at the starting while elements greater than 5 are arranged after them without changing the relative order of all the elements.``````

### SOLVING APPROACH:

BRUTE FORCE METHOD:

1. The idea is to create two additional arrays `min_arr` and `max_arr` for storing the elements less than `X` in `min_arr` while to store elements greater than or equal to `X` in `max_arr`.
2. Then simply print elements from `min_arr` first and then `max_arr`.
3. This approach is not `efficient` as it uses additional `O(N)` space.

### SOLUTIONS:

```
#include <bits/stdc++.h>
using namespace std;
typedef struct Node {
int data;
struct Node *next;
}Node;
Node* temp = NULL;
Node* insert(Node *head, int data) {
}
Node* node = new Node();
node->data = data;
node->next = NULL;
temp->next = node;
temp = temp->next;
}

cout << head->data << " ";
return;
}
cout << head->data << " ";
}

Node* ArrangeSalary(Node* head, int X) {

vector<int> v_min, v_max;
while(temp != NULL){
if(temp->data < X)
v_min.push_back(temp->data);
else
v_max.push_back(temp->data);
temp = temp->next;
}

while(temp != NULL){
if(!v_min.empty()){
temp->data = v_min.front();
v_min.erase(v_min.begin());
}
else if(!v_max.empty()){
temp->data = v_max.front();
v_max.erase(v_max.begin());
}

temp = temp->next;
}

}

int main()
{

Node *ptr = NULL;
int n, X;
cin >> n >>X;
for(int i=0; i<n; i++) {
int data;
cin >> data;
}
cout << endl;
return 0;
}
```

EFFICIENT METHOD:

1. The idea is to create two linked list and initialize their head nodes as NULL –

• `smaller` list of values smaller than `X`.
• `larger` list of values greater than or equal to `X`.
2. Now traverse the original list and if an element is less than `X`, append it to the end of the `smaller` list else append it to the end of the `larger` list. Finally concatenate both the `smaller` and `larger` lists to form the resultant list.

### SOLUTIONS:

```
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
}Node;
{
Node *element = (Node*) malloc(sizeof(Node));
element->data = val ;
element->next = NULL ;
if ( head == NULL ) {
}
while (temp->next != NULL)
temp = temp->next ;
temp->next = element ;
element->next = NULL ;
}

return;
}
}

Node* ArrangeSalary(Node* head, int X) {

/* if list has 0 or 1 elements then return */

/* create two lists one for storing smaller elements than X and
another for storing greater than or equal to elements than X */

/* head pointer for smaller list */
Node *smaller = NULL ;

/*pointer to the last element in the smaller list */
Node *temp_smaller;

/* head pointer for greater list */
Node *greater = NULL ;

/*pointer to the last element in the greater list */
Node *temp_greater ;

while(temp != NULL){
Node* t = temp;
temp = temp -> next;

if(t->data < X){
if(smaller == NULL){
smaller = t;
temp_smaller = t;
t -> next = NULL;
}
else{
temp_smaller -> next = t;
t -> next = NULL;
temp_smaller = t;
}

}
else{
if(greater == NULL){
greater = t;
temp_greater = t;
t -> next = NULL;
}
else{
temp_greater -> next = t;
t -> next = NULL;
temp_greater = t;
}
}
}

/* concatenating both smaller and greater lists */
temp_smaller -> next = greater;

return smaller;

}
int main()
{

int n, X;
scanf("%d %d", &n,&X);
for(int i=0; i<n; i++) {
int data;
scanf("%d", &data);
}
printf("\n");
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;
typedef struct Node {
int data;
struct Node *next;
}Node;
Node* temp = NULL;
Node* insert(Node *head, int data) {
}
Node* node = new Node();
node->data = data;
node->next = NULL;
temp->next = node;
temp = temp->next;
}

cout << head->data << " ";
return;
}
cout << head->data << " ";
}

Node* ArrangeSalary(Node* head, int X) {

/* if list has 0 or 1 elements then return */

/* create two lists one for storing smaller elements than X and
another for storing greater than or equal to elements than X */

/* head pointer for smaller list */
Node *smaller = NULL ;

/*pointer to the last element in the smaller list */
Node *temp_smaller= NULL;

/* head pointer for greater list */
Node *greater = NULL ;

/*pointer to the last element in the greater list */
Node *temp_greater = NULL;

while(temp != NULL){
Node* t = temp;
temp = temp -> next;

if(t->data < X){
if(smaller == NULL){
smaller = t;
temp_smaller = t;
t -> next = NULL;
}
else{
temp_smaller -> next = t;
t -> next = NULL;
temp_smaller = t;
}

}
else{
if(greater == NULL){
greater = t;
temp_greater = t;
t -> next = NULL;
}
else{
temp_greater -> next = t;
t -> next = NULL;
temp_greater = t;
}
}
}

/* concatenating both smaller and greater lists */
temp_smaller -> next = greater;

return smaller;
}

int main()
{

Node *ptr = NULL;
int n, X;
cin >> n >>X;
for(int i=0; i<n; i++) {
int data;
cin >> data;
}
cout << endl;
return 0;
}
```
```
import java.io.*;
import java.util.*;

public class Main {
public int value;

this.value = nodeData;
this.next = null;
}
}

this.tail = null;
}

public void insertNode(int nodeData) {

} else {
this.tail.next = node;
}

this.tail = node;
}
}

while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
System.out.println();
}

/* if list has 0 or 1 elements then return */

/* create two lists one for storing smaller elements than X and
another for storing greater than or equal to elements than X */

/* head pointer for smaller list */

/*pointer to the last element in the smaller list */

/* head pointer for greater list */

/*pointer to the last element in the greater list */

while(temp != null){
temp = temp.next;

if(t.value < X){
if(smaller == null){
smaller = t;
temp_smaller = t;
t.next = null;
}
else{
temp_smaller.next = t;
t.next = null;
temp_smaller = t;
}

}
else{
if(greater == null){
greater = t;
temp_greater = t;
t.next = null;
}
else{
temp_greater.next = t;
t.next = null;
temp_greater = t;
}
}
}

/* concatenating both smaller and greater lists */
temp_smaller.next = greater;

return smaller;
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {

int size = scanner.nextInt();
int X = scanner.nextInt();

for (int i = 0; i < size; i++) {
int llistItem = scanner.nextInt();

llist.insertNode(llistItem);
}
Space Complexity: `O(1)`