Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Sum Between Zeroes

Easy

0/40

Average time to solve is 20m

Contributed by

32 upvotes

Asked in companies

Problem statement

You are given a Singly Linked List which contains a series of integers separated by ‘0’.

Between two zeroes, you have to merge all the nodes lying between them into a single node which contains the sum of all the merged nodes. You have to perform this in place.

Note:

It is guaranteed that there will be no two consecutive zeroes, and there will always be a zero at the beginning and end of the linked list.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains the elements of the singly linked list separated by a single space. The -1 indicates the end of the singly linked list and hence, would never be a list element.

Output Format:

The first and the only output line contains the integers present in the linked list after all the merging operations have been performed.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

3 <= N <= 10^5
0 <= VAL <= 10^3

Where 'VAL' represents the integers present in the list.

Time limit: 1 sec

Sample Input 1:

0 1 2 3 0 4 5 0 6 0 -1

Sample Output 1:

6 9 6 -1

Explanation Of Sample Input1:

The given linked list is:
0 -> 1 -> 2 -> 3 -> 0 -> 4 -> 5 -> 0 -> 6 -> 0 -> null
Then, the linked list is converted to:
6 -> 9 -> 6 -> null
Taking 0s as the start and end in reference to a sequence, we can see that there are 3 sequences. They are:
 1. 1 -> 2 -> 3, which sum to 6
 2. 4 -> 5, which sum to 9
 3. 6, which sum to 6 only

Sample Input 2:

0 1 2 4 8 16 0 -1

Sample Output 2:

31 -1

Hint 1

Let’s not think of merging nodes, but rather transferring their contents into a single node. Can you think of an approach to do this by maintaining two pointers?

Approaches (1)

Approach 1

Two Pointer Approach

Let us initialize two pointers, newHead and newTail, with NULL (These will be the head and tail of the final list). Now traverse the given list. Ignore the first zero. Now, as you encounter non-zero nodes, add their values in a variable called ‘sum’. As soon as you encounter a node with data 0, change that node's value to ‘sum’, and

If newHead is NULL, this node becomes the new head and tail of the list
If newHead is not NULL, then connect this node with the tail of the list and assign it to be the new tail

Follow this algorithm for the rest of the list.

Note that we are not creating a new list, because we don’t create new nodes, we simply change the values of existing nodes and modify their connections.

Time Complexity

O(N), where N is the size of the linked list.

Traversing the linked list once takes O(N) time.

Space Complexity

O(1), as constant extra space is required.

(100% EXP penalty)

Sum Between Zeroes

Simi Princy

Interview problems

Java Solution

public class Solution  {

    public static LinkedListNode<Integer> sumBetweenZeros(LinkedListNode<Integer> head) {
        //Write your code here
        LinkedListNode<Integer>  dummy = new LinkedListNode<Integer> (0);
        LinkedListNode<Integer>  curr = dummy;
        LinkedListNode<Integer> temp = head;
        int sum =0;
        while(temp != null) {
            if(temp.data != 0) {
                sum += temp.data;
            }
            if(temp.data == 0) {
                head = temp.next;
                 if(sum > 0){
                curr.next = new  LinkedListNode<Integer>(sum);
                curr = curr.next;
            }
                sum = 0;
            }
            temp=temp.next;
        }
        return dummy.next;

    }

}

20 views

0 replies

0 upvotes

Rahul Lodhi

Interview problems

java solution | straight forward

public class Solution  {

    public static LinkedListNode<Integer> sumBetweenZeros(LinkedListNode<Integer> head) {
        //Write your code here
        LinkedListNode<Integer> p = head;
        int sum=0;
        LinkedListNode<Integer> dummy = new LinkedListNode<Integer>(-1);
        LinkedListNode<Integer> newHead = dummy;
        while(p!=null){
            if(p.data==0 && sum!=0){
                LinkedListNode<Integer> temp = new LinkedListNode<Integer>(sum);
                dummy.next = temp;
                dummy = dummy.next;
                sum=0;
            }
            sum += p.data;
            p=p.next;
        }
        return newHead.next;
    }

}

27 views

0 replies

1 upvote

Ankit Kumar

Interview problems

C++ Code || Easy || Optimal Approach

Node* sumBetweenZeroes(Node* head)

{

int sum=0;

Node* curr=head;

Node* temp=curr->next;

Node* prev=NULL;

while(curr->next!=NULL){

sum=0;

while(temp->data!=0){

sum+=temp->data;

temp=temp->next;

}

curr->data=sum;

curr->next=temp;

prev=curr;

curr=curr->next;

temp=temp->next;

}

prev->next=NULL;

return head;

}

113 views

0 replies

0 upvotes

Arpit Kumar

Interview problems

Simple cpp solution

Node* sumBetweenZeroes(Node* head)

{

Node *fast = head->next;

Node *slow = head;

Node *localstart = nullptr;

int sum = 0;

while(fast)

{

if(fast->data!=0){

sum+=fast->data;

}

else{

slow->data = sum;

sum =0;

localstart = slow;

slow = slow->next;

}

fast = fast->next;

}

Node *temp = localstart->next;

localstart->next = nullptr;

while(temp)

{

Node *temp2 = temp->next;

delete temp;

temp=temp->next;

}

return head;

}

80 views

0 replies

0 upvotes

Amit Raj

Interview problems

Time efficient approach || C++

//Runtime better than 96.85%, Memory better than 38.44%

Node* sumBetweenZeroes(Node* head){
if(head->data==0){
        head = head->next;
    }
    Node* result = NULL;
    Node* last = NULL;
    Node* temp = head;
    Node* zeroptr = NULL;


    while (temp != NULL) {
        int sum = 0;
        int count = 0;
        while (temp != NULL && temp->data != 0) {
            sum += temp->data;
            temp = temp->next;
            if(temp!=NULL&&temp->data==0){
                zeroptr = temp;
                count = 1;
            }
        }
            Node* newNode = new Node(sum);
            if (result == NULL) {
                if(count==0){
                    return head;
                }
                result = newNode;
                last = newNode;
            } else {
                if(count==0){
                 last->next = zeroptr->next;
                 return result;
                }
                last->next = newNode;
                last = newNode;
            }
        if (temp != NULL) {
            temp = temp->next;
        }
    }
    return result;
}

programming

86 views

0 replies

2 upvotes

Gokul R

Interview problems

Easy Python Approach

class Node :
    def __init__(self, data) :
        self.data = data
        self.next = None


def sumBetweenZeroes(head) :
    # taking some pointers to keep track of curr and zero nodes
    curr = head
    # first zero is skipped
    zero = head.next
    # taking sumNode as 0
    sumNode = 0
    # looping until the list becomes empty
    while zero:
        # checking if zero's data is not 0
        if zero.data != 0:
            # adding zero's data to sumNode
            sumNode += zero.data
        # else zero's data is 0
        else:
            # zero's data is updated to sumNode and is linked
            # with curr node by skipping in between nodes
            zero.data = sumNode
            curr.next = zero
            # curr pointer is updated and sumNode is reset to 0
            curr = curr.next
            sumNode = 0
        # zero pointer is updated for next iteration
        zero = zero.next
        
    # returning the head node of the changed Linked List
    return head.next

python

49 views

0 replies

0 upvotes

Imran Hasan

Interview problems

What's Up

Node* sumBetweenZeroes(Node* head) 
{

        Node* right = head->next,*left = head;
        int total = 0;
        while(right){
            if(right->data) total+=right->data;

            else{
                left->data = total;
                total=0;
                left->next = right->next;
                left=left->next;
             }
        
            right=right->next;
        }
        return head;

}

62 views

0 replies

0 upvotes

Sanjay Balam

C++ solution

Node* sumBetweenZeroes(Node* head) {

Node *dummy = new Node(0);

Node *newhead = dummy;

Node *curr=head;

curr=curr->next;

int sum=0;

while(curr!=NULL){

while(curr->data!=0){

sum+=curr->data;

curr=curr->next;

}

newhead->next=new Node(sum);

newhead=newhead->next;

curr=curr->next;

sum=0;

}

return dummy->next;

}

108 views

0 replies

0 upvotes

Aaditya Surana

Interview problems

Python easy solution

def sumBetweenZeroes(head) :
    dummy=Node(0)
    newhead=dummy
    curr=head
    curr=curr.next
    Sum=0

    while curr is not None:
        while curr.data!=0:
            Sum+=curr.data
            curr=curr.next

        newhead.next=Node(Sum)
        newhead=newhead.next
        curr=curr.next
        Sum=0

    return dummy.next

47 views

0 replies

0 upvotes

Abhi shikth

Interview problems

Simple Code (java)

public static LinkedListNode<Integer> sumBetweenZeros(LinkedListNode<Integer> head) {

//Write your code here

int sum = 0;

LinkedListNode<Integer> dummy = new LinkedListNode<Integer>(0);

LinkedListNode<Integer> temp = dummy;

LinkedListNode<Integer> curr = head;

while(curr != null && curr.next != null)

{

if(curr.data == 0) sum = 0;

else sum += curr.data;

if(curr.next.data == 0)

{

LinkedListNode<Integer> newnode = new LinkedListNode<Integer>(sum);

temp.next = newnode;

temp = temp.next;

}

curr = curr.next;

}

return dummy.next;

}

68 views

0 replies

0 upvotes

Console