DEV Community

Cover image for Add 1 to the Number(Wrapped in linked List)
Aastha Talwaria
Aastha Talwaria

Posted on

3 3

Add 1 to the Number(Wrapped in linked List)

Add one to the Number wrapped in LinkedList

(Benefits of LinkedList: no limits for a number)
Given a linked list denoting a number (each key will have numbers from 0-9), implement a function for adding 1 to it.
Example - For number 7899, Linked List would be [7, 8, 9, 9]
If you add 1 to 7899, you get 7900 which is [7, 9, 0, 0]

Input1:  [7, 8, 9, 9]
Output1: [7, 9, 0, 0]
Enter fullscreen mode Exit fullscreen mode

My Approach:

  • The idea is to solve the problem by the backtracking technique.
  • As when we add the multi-digit number, we start from the end. Thus, carrying a borrow from last to first digit we get our answer. I will follow the same approach in my code.

CODE:

//function converting nums in linkedList
function getLinkedList ( ...arr ) {
    let nodesArray = [];
    for( var index=0; index<arr.length; index++ ) {
        nodesArray.push({
            digit: arr[index],
            next:null
        })
    }
    for( var index = 0; index < nodesArray.length-1; index++ ) {
        nodesArray[index].next = nodesArray[index+1];
    }
    if(nodesArray.length){
        return nodesArray[0];
    }
}
//prints the linkedList's digits in an Array.
function printList(list) {
    let arr = [], node = list;
    while(node != null) {
        arr.push(node.digit);
        node = node.next;
    }
    console.log(arr);
}
let list = getLinkedList(7, 8, 9, 9);

printList(list); // [7, 8, 9, 9]

let num =1;//number to be added

//function which will add one to the number
function addOne(_list) {
    //to achieve backtracking calling function before implementation till end
    if(_list.next != undefined){
        addOne(_list.next);
    }
    _list.digit += num;
    //borrow will be in case of sum 10 or greater than ten
    if(_list.digit>10){
        _list.digit = 10-_list.digit;
        num = 1;
    } else if(_list.digit=== 10){
        _list.digit = 0;
        num = 1;
    } else {////borrow will be zero when sum is less than 10
        num =0;
    }
    //to handle all nine case, 
    //example in case of 9999, answer will be 10000
    if(list === _list && num!= 0 ){
        //creating new node for the last borrow (1), in case of all nine
        list = {
            digit : num,
            next: list
        }
    }
}
addOne(list);
printList(list); // [7, 9, 0, 0]
//in case of[9, 9, 9, 9], the output is [1,0,0,0,0] 
Enter fullscreen mode Exit fullscreen mode

Let's discuss your approach in the discussion box or you can hit me up at aastha.talwaria29@gmail.com.

Thanks for reading.

A Layered Approach to Mobile App Protection

A Layered Approach to Mobile App Protection

Attackers use static analysis to understand how your app functions and the data it contains. By using multiple layers of protections like code obfuscation and string encryption, you can prevent attackers from accessing your app.

Read more

Top comments (0)

SurveyJS custom survey software

JavaScript Form Builder UI Component

Generate dynamic JSON-driven forms directly in your JavaScript app (Angular, React, Vue.js, jQuery) with a fully customizable drag-and-drop form builder. Easily integrate with any backend system and retain full ownership over your data, with no user or form submission limits.

Learn more

👋 Kindness is contagious

Explore this insightful write-up, celebrated by our thriving DEV Community. Developers everywhere are invited to contribute and elevate our shared expertise.

A simple "thank you" can brighten someone’s day—leave your appreciation in the comments!

On DEV, knowledge-sharing fuels our progress and strengthens our community ties. Found this useful? A quick thank you to the author makes all the difference.

Okay