Count Triplets in a Sorted Doubly Linked List

You are provided with an integer X and a non-decreasing sorted doubly linked list consisting of distinct nodes.

Your task is to find and return the count of triplets within the list that sum up to the value X.

Input:

The first line contains an integer T representing the number of test cases. For each test case:

- The first line contains an integer X.

- The second line contains elements of the doubly linked list separated by a space, ending with -1. Note: -1 is not part of the list.

Output:

For each test case, output a single integer on a new line denoting the number of triplets with a sum equal to X.

Example:

Input:

T = 1 X = 6 1 2 3 4 -1

Output:

1

Explanation:

The triplet (1, 2, 3) sums up to the value 6.

Constraints:

1

Question

Count Triplets in a Sorted Doubly Linked List

You are provided with an integer X and a non-decreasing sorted doubly linked list consisting of distinct nodes.

Your task is to find and return the count of triplets within the list that sum up to the value X.

Input:

The first line contains an integer T representing the number of test cases. For each test case:

- The first line contains an integer X.

- The second line contains elements of the doubly linked list separated by a space, ending with -1. Note: -1 is not part of the list.

Output:

For each test case, output a single integer on a new line denoting the number of triplets with a sum equal to X.

Example:

Input:

T = 1
X = 6
1 2 3 4 -1

Output:

Explanation:

The triplet (1, 2, 3) sums up to the value 6.

Constraints:

1 <= T <= 5
1 <= N <= 10^3
-3 * 10^5 <= X <= 3 * 10^5
-10^5 <= data <= 10^5 and data != -1

Where N is the number of nodes in the given linked list, and X is the required triplet sum value.

Note: No need to print anything; focus on implementing the function.

Accepted Answer

int count=0;
    DLLNode* temp=head;
    while(temp->next!=NULL){
        temp=temp->next;
    }
    DLLNode* first=head;
    DLLNode* second=first->next;
    DLLNode* last=temp;
    while(second!=last){
        DLLNode* temp1=second;
        DLLNode* temp2=last;
        while(seconddata+temp1->data+temp2->data==x){
                count++;
               temp2=temp2->prev;
               temp1=temp1->next;
            }
            else if((first->data+temp1->data+temp2->data)>x){
                temp2=temp2->prev;
            }
            else{
                temp1=temp1->next;
            }
        }
        first=first->next;
        second=second->next;

    }
    return count;

Count Triplets in a Sorted Doubly Linked List

Input:

Output:

Example:

Input:

Output:

Explanation:

Constraints:

Top Amazon Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Amazon Software Developer Intern