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]
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]
Let's discuss your approach in the discussion box or you can hit me up at aastha.talwaria29@gmail.com.
Thanks for reading.
Top comments (0)