The moment you said how we do this in basic maths - I paused the video and did a couple of dry runs and I was able to code both the approaches on my own, thankyou so much Striver! ❤
Man oh man! One silly question, do you think of all these solutions by yourself? Sometimes looking at your explanations, i feel unreal because they so good
An alternative solution without recursion or reversing the linked list. It includes traversing the linked list intially and maintaining a pointer with the last Non 9 element . After traversing the complete linked list we have three cases : CASE 1 : Last element is not 9 : Simply add the last data value and do nothing CASE 2 : Last element is 9 and there is a non9 element (its not null) : increase the last non 9 element by one (we have its reference) and traverse till the end making all data values as 0 CASE 3 : Last element in 9 and there in non non9 element (it is null) : insert 1 at the start of the linkedlist and make all other element 0. Code for the same : class Solution { public static Node addOne(Node head) { Node h = head; Node lastNonNine = null; while(head.next!=null) { if(head.data !=9) { lastNonNine = head; } head = head.next; } if(head.data !=9) { head.data = head.data + 1; return h; } else { if(lastNonNine !=null) { lastNonNine.data = lastNonNine.data + 1; lastNonNine = lastNonNine.next; while(lastNonNine != head) { lastNonNine.data = 0; lastNonNine = lastNonNine.next; } head.data = 0; return h; } else { Node temp = new Node(1); temp.next = h; lastNonNine = h; while(lastNonNine != head) { lastNonNine.data = 0; lastNonNine = lastNonNine.next; } head.data = 0; return temp; } } } }
int carry(Node* &temp){ //base case if(!temp->next){ int sum=temp->data+1; temp->data=sum%10; return sum/10; } int helper=carry(temp->next); if(!helper) return 0; int sum=temp->data+ helper; temp->data=sum%10; return sum/10; } Node *addOne(Node *head) { int x=carry(head); if(x) { Node* last_bit= new Node(x); last_bit->next=head; return last_bit; } return head; } //if anyone's looking for the recursive code ,i have written it ,nice video
Implemented the helper function in my own way class Solution { public: int helper(Node *temp){ if(temp==NULL)return 1; int sum=helper(temp->next)+temp->data; temp->data=sum%10; return sum/10; } Node* addOne(Node* head) { int carry=helper(head); if(carry==1){ Node * newNode=new Node(1); newNode->next=head; return newNode; } return head; } };
we are using reverse(head) function and that uses a recursive approach then why that iterative solution doesn't uses a space complexity of O(2n) as we are using this recursive reverse(head) function 2 times?????
I have solved it Using two pointer Time complexity --O(2N) only if the all number in the list is 9 otherwise O(N) Space complexity -0(1); class Solution { public Node addOne(Node head) { // code here. Node nine=head.next; Node notnine=head; while(nine!=null){ if(nine.data==9){ nine=nine.next; } else{ notnine=nine; nine=nine.next; } } int temp=head.data; while(notnine!=null){ if(notnine.data==9){ notnine.data=0; } else{ notnine.data=notnine.data+1; } notnine=notnine.next; } Node newnode=new Node(1); Node temp2=head; if(head.data==0&&temp==9){ head=newnode; newnode.next=temp2; } return head; } }
class Solution { public: int findans(Node *&head){ if(!head){ return 1; } int c = findans(head -> next); int sum = c + head -> data; head -> data = sum % 10; return sum / 10; } Node* addOne(Node *head) { int car = findans(head); if(car){ Node *n = new Node(1); n -> next = head; head = n; } return head; } };
can we not use stack instead of recursion?? here's the code: class Solution: def addOne(self, head): if head is None: return ListNode(1) st = [] curr = head while curr is not None: st.append(curr) curr = curr.next carry = 1 while carry and st: node = st.pop() curr_val = node.val + carry node.val = curr_val % 10 carry = curr_val // 10 if carry == 0: break
if carry: head = ListNode(1, head)
return head In recursion the best case is also taking 2N time but here it can be O(1), we will break the loop as soon as the carry becomes 0.
def helpp(self,temp): if(temp==None): return 1 carry=self.helpp(temp.next) summ=temp.data+carry temp.data=summ%10 if(summ>=10): return 1 else: return 0 def addOne(self,head): #Returns new head of linked List. carry=self.helpp(head) if(carry==1): p=Node(1) p.next=head return p return head can any one tell why my code is not passing some testcases in gfg
Almost solved the entire series just 5 questions remaining thanks to you brother ❤❤❤❤
The moment you said how we do this in basic maths - I paused the video and did a couple of dry runs and I was able to code both the approaches on my own, thankyou so much Striver! ❤
Thanks Striver!!!!!!!!!!! You are a rare gem!
Man oh man! One silly question, do you think of all these solutions by yourself? Sometimes looking at your explanations, i feel unreal because they so good
Such a great logic of using recursion! Ur a man with a great vision. Thank you striver
Explanation recursion by Striver is another level🔥🔥.
Respected Sir, You and your work is great.
I have made the recursive code by myself ,thanks striver for providing amazing content..
Too good explanation sir
you don't know how much you are helping me with this playlist
The way you teaching recursive is different ❣️
😍😍😍😍😍God of dsa
An alternative solution without recursion or reversing the linked list. It includes traversing the linked list intially and maintaining a pointer with the last Non 9 element .
After traversing the complete linked list we have three cases :
CASE 1 : Last element is not 9 : Simply add the last data value and do nothing
CASE 2 : Last element is 9 and there is a non9 element (its not null) : increase the last non 9 element by one (we have its reference) and traverse till the end making all data values as 0
CASE 3 : Last element in 9 and there in non non9 element (it is null) : insert 1 at the start of the linkedlist and make all other element 0.
Code for the same :
class Solution
{
public static Node addOne(Node head)
{
Node h = head;
Node lastNonNine = null;
while(head.next!=null)
{
if(head.data !=9)
{
lastNonNine = head;
}
head = head.next;
}
if(head.data !=9)
{
head.data = head.data + 1;
return h;
}
else {
if(lastNonNine !=null)
{
lastNonNine.data = lastNonNine.data + 1;
lastNonNine = lastNonNine.next;
while(lastNonNine != head)
{
lastNonNine.data = 0;
lastNonNine = lastNonNine.next;
}
head.data = 0;
return h;
}
else
{
Node temp = new Node(1);
temp.next = h;
lastNonNine = h;
while(lastNonNine != head)
{
lastNonNine.data = 0;
lastNonNine = lastNonNine.next;
}
head.data = 0;
return temp;
}
}
}
}
yes i have done by this way
very long code
It contains to much check condition which reduce the readability and understanding
@@DrOnZeR2022
Node* addOne(Node *head)
{
Node *temp = head, *last = nullptr;
while(temp) {
if(temp->data != 9) last = temp;
temp = temp->next;
}
if(last == nullptr) {
Node *newHead = new Node(1);
newHead->next = head;
while(head) {
head->data = 0;
head = head->next;
}
return newHead;
}
else {
last->data += 1;
Node *makezero = last->next;
while(makezero) {
makezero->data = 0;
makezero = makezero->next;
}
return head;
}
}
Lecture successfully completed on 28/11/2024 🔥🔥k
Understood,thanks striver for this amazing video.
Really inspiring striver ❤..
I just cant express how much we people love you.
Thank you so much 🙌🥹
Understood both recursive and iterative approach!!😇Recursive one is a bit confusing but feels easier once you understand it
int carry(Node* &temp){
//base case
if(!temp->next){
int sum=temp->data+1;
temp->data=sum%10;
return sum/10;
}
int helper=carry(temp->next);
if(!helper) return 0;
int sum=temp->data+ helper;
temp->data=sum%10;
return sum/10;
}
Node *addOne(Node *head)
{ int x=carry(head);
if(x) {
Node* last_bit= new Node(x);
last_bit->next=head;
return last_bit;
}
return head;
} //if anyone's looking for the recursive code ,i have written it ,nice video
great level of explanation sir!!!!
Implemented the helper function in my own way
class Solution {
public:
int helper(Node *temp){
if(temp==NULL)return 1;
int sum=helper(temp->next)+temp->data;
temp->data=sum%10;
return sum/10;
}
Node* addOne(Node* head) {
int carry=helper(head);
if(carry==1){
Node * newNode=new Node(1);
newNode->next=head;
return newNode;
}
return head;
}
};
there is a question on LC named ADD TWO NUMBERS II. Only difference is you need to add two numbers from end. Understood
In case of Error: replace addNode method to addOne
🤣
Understood. Thanks Striver.
Sorry sir but you didn't upload the solution sheet for this problem please upload it
Understood striver bhai
Just Amazing❤
Enjoying the playlist, please make playlist for trees, graphs please please
already exists in hisn channel
I think Recursive solution is overcomplicated for this problem.
amazing explaination
Coding Ninjas Java Compiler not working for this problem, but i have understood totally thank you
just use addone for method
i had done the recursion one and the space complexity will be O(N) due to the recursion stack and this pisses me off ----''__''
super bro keep it up posting🎉🎉
we are using reverse(head) function and that uses a recursive approach then why that iterative solution doesn't uses a space complexity of O(2n) as we are using this recursive reverse(head) function 2 times?????
somebody know this then please reply....
We can reverse a LL in iterative way as well without taking any extra space. Watch his "reverse a Linked list" video, you will get it.
UNDERSTOOD SIR
Understood✅🔥🔥
Very Well Understood
Understood, thank you.
I have solved it Using two pointer
Time complexity --O(2N) only if the all number in the list is 9 otherwise O(N)
Space complexity -0(1);
class Solution {
public Node addOne(Node head) {
// code here.
Node nine=head.next;
Node notnine=head;
while(nine!=null){
if(nine.data==9){
nine=nine.next;
}
else{
notnine=nine;
nine=nine.next;
}
}
int temp=head.data;
while(notnine!=null){
if(notnine.data==9){
notnine.data=0;
}
else{
notnine.data=notnine.data+1;
}
notnine=notnine.next;
}
Node newnode=new Node(1);
Node temp2=head;
if(head.data==0&&temp==9){
head=newnode;
newnode.next=temp2; }
return head;
}
}
Thank you Bhaiya
class Solution
{
public:
int findans(Node *&head){
if(!head){
return 1;
}
int c = findans(head -> next);
int sum = c + head -> data;
head -> data = sum % 10;
return sum / 10;
}
Node* addOne(Node *head)
{
int car = findans(head);
if(car){
Node *n = new Node(1);
n -> next = head;
head = n;
}
return head;
}
};
Naive solution
Node *reverse(Node* head){
if(head == NULL || head->next ==NULL){
return head;
}
Node *newhead = reverse(head->next);
Node* front = head->next;
front->next = head;
head->next = NULL;
return newhead;
}
Node *addOne(Node *head)
{
// naive solution
head = reverse(head);
Node* temp = head;
int carry = 1;
while(temp!=NULL){
temp->data = temp->data+carry;
if(temp->datadata =0;
carry =1;
}
temp= temp->next;
}
if(carry ==1){
Node* newNode= new Node(1);
head = reverse(head);
newNode->next = head;
return newNode;
}
head = reverse(head);
return head;
}
// better solution using recursion
int helper(Node* temp, int &carry){
if(temp == NULL){
return 1;
}
carry = helper(temp->next,carry);
temp->data = temp->data+carry;
if(temp->data data=0;
return 1;
}
}
Node *addOne(Node *head)
{
/* better solution */
int carry=0;
carry = helper(head,carry);
if(carry ==1){
Node* newNode= new Node(1);
newNode->next = head;
return newNode;
}
return head;
}
can we not use stack instead of recursion??
here's the code:
class Solution:
def addOne(self, head):
if head is None:
return ListNode(1)
st = []
curr = head
while curr is not None:
st.append(curr)
curr = curr.next
carry = 1
while carry and st:
node = st.pop()
curr_val = node.val + carry
node.val = curr_val % 10
carry = curr_val // 10
if carry == 0:
break
if carry:
head = ListNode(1, head)
return head
In recursion the best case is also taking 2N time but here it can be O(1), we will break the loop as soon as the carry becomes 0.
thank you so much bhaiya
UNDERSTOOD;
class Solution
{
public static Node addOne(Node head)
{
Node temp = head;
int[] carry = new int[1];
carry[0] = 1;
addOne(temp,carry);
if(carry[0]>0){
Node newNode = new Node(carry[0]);
newNode.next = head;
return newNode;
}
return head;
}
public static void addOne(Node root, int[] carry){
if(root==null) return;
addOne(root.next,carry);
if(carry[0]==0) return;
int sum = (root.data+carry[0]);
root.data = sum%10;
carry[0] = sum/10;
}
}
Why am I not able to think medium questions like this
Me too I just can't seem to think the solution .I mostly got blank no matter how much i try......
Understood 😃😃😃😃
Code is not present in links so here is java
class Solution
{
public static Node rev(Node head) {
Node temp = head;
Node prev = null;
while(temp != null){
Node front = temp.next;
temp.next = prev;
prev = temp;
temp = front;
}
return prev;
}
public static Node addOne(Node head)
{
if(head==null)return null;
head=Solution.rev(head);
Node tm=head;
int carry=1;
while(tm!=null){
tm.data=tm.data+carry;
if(tm.data0){
Node n=new Node (carry);
n.next=head;
head=n;
}
return head;
}
}
thankyou
Understood!
An alternate solution for this Problem without recursion.
Node* reverseLL(Node* head){
if(head==NULL||head->next==NULL){
return head;
}
Node* newhead=reverseLL(head->next);
Node* front=head->next;
front->next=head;
head->next=NULL;
return newhead;
}
Node *addOne(Node *head)
{
head=reverseLL(head);
Node* temp=head;
int carry=1;
int sum=0;
int newval;
while(carry!=0&&temp!=NULL){
sum=carry+temp->data;
newval=sum%10;
temp->data=newval;
carry=sum/10;
temp=temp->next;
}
if(carry){
head=reverseLL(head);
Node*newnode=new Node(carry,head);
head=newnode;
}
else{
head=reverseLL(head);
}
return head;
}
Without reversing the LL and SC-O(1) & Tc-O(2n)
class Solution {
public:
Node* addOne(Node* head) {
Node* temp=head;
Node* pos=nullptr;
int val;
while(temp->next){
val=temp->next->data;
if(val==9){
if(!pos) pos=temp;
}
else pos=nullptr;
temp=temp->next;
}
if(!pos) pos=temp;
if(pos==head){
if(head->data==9){
Node* newH=new Node(1);
newH->next=head;
// head->data=0;
head=newH;
}
}
val=pos->data; ++val;
pos->data=val%10;
pos=pos->next;
while(pos){
pos->data=0;
pos=pos->next;
}
return head;
}
};
Where are the notes
gem video
Undertsood
def helpp(self,temp):
if(temp==None):
return 1
carry=self.helpp(temp.next)
summ=temp.data+carry
temp.data=summ%10
if(summ>=10):
return 1
else:
return 0
def addOne(self,head):
#Returns new head of linked List.
carry=self.helpp(head)
if(carry==1):
p=Node(1)
p.next=head
return p
return head
can any one tell why my code is not passing some testcases in gfg
why doing mod 10? just check if it is equal to 10 and then proceed with logic.
I used a different logic
Node* addOne(Node* head)
{
Node* tail = head;
while(tail->next != NULL)
{
tail = tail->next;
}
if (tail->data < 9)
{
tail->data = tail->data + 1;
return head;
}
Node* last_element_prev_to_9 = NULL;
Node* temp = head;
while(temp->next != NULL)
{
if ((temp->next->data == 9) && (temp->data != 9))
{
last_element_prev_to_9 = temp;
}
temp = temp->next;
}
if (last_element_prev_to_9 != NULL)
{
last_element_prev_to_9->data += 1;
Node* temp = last_element_prev_to_9->next;
while(temp != NULL)
{
temp->data = 0;
temp = temp->next;
}
return head;
}
Node* dummy = new Node(1);
Node* curr = head;
while(curr != NULL)
{
curr->data = 0;
curr = curr->next;
}
dummy->next = head;
return dummy;
}
Understood
Understood Man you damn it!!!!\
understood.
Striver Bhai apana Bhadrak ru na
I am also from Bhadrak
Where did you get the idea that he is from Bhadrak?
❤❤
❤
undeerstood
US
respect ++;
us
god
Godly🙏🪄❤
public int addHelper(Node temp){
if(temp == null){
return 1;
}
int carry = addHelper(temp.next);
temp.data = temp.data+carry;
if(temp.data < 10) return 0;
temp.data = 0;
return 1;
}
public static Node addOne(Node head) {
// Write your code here.
Solution solution = new Solution();
int carry = solution.addHelper(head);
if(carry == 1){
Node newNode = new Node(1);
newNode.next = head;
head = newNode;
}
return head;
}
BRUTE FORCE ==>
```
import java.math.BigInteger;
import java.util.List;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class add1ToLL {
public static ListNode addOne(ListNode head) {
if (head == null) {
return new ListNode(1);
}
// Reverse the linked list
head = reverseLL(head);
ListNode temp = head;
int carry = 1;
// Traverse the list and add one
while (temp != null) {
temp.val = temp.val + carry;
if (temp.val < 10) {
carry = 0;
break;
} else {
temp.val = 0;
carry = 1;
}
if (temp.next == null && carry == 1) {
temp.next = new ListNode(0); // Add new node if needed
}
temp = temp.next;
}
// Reverse the linked list again to restore original order
head = reverseLL(head);
// If there is still a carry, add a new node at the front
if (carry == 1) {
ListNode newNode = new ListNode(1);
newNode.next = head;
return newNode;
}
return head;
}
private static ListNode reverseLL(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode next;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Helper method to create a linked list from an array.
public static ListNode createLinkedList(int[] values) {
if (values.length == 0)
return null;
ListNode head = new ListNode(values[0]);
ListNode current = head;
for (int i = 1; i < values.length; i++) {
current.next = new ListNode(values[i]);
current = current.next;
}
return head;
}
// Helper method to print the linked list.
public static void printLinkedList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.val);
current = current.next;
if (current != null) {
System.out.print("->");
}
}
System.out.println();
}
public static void main(String[] args) {
// Test case 1: LinkedList 4->5->6
int[] list1 = { 9 };
ListNode head1 = createLinkedList(list1);
System.out.print("Before: ");
printLinkedList(head1);
head1 = addOne(head1);
System.out.print("After: ");
printLinkedList(head1);
// Test case 2: LinkedList 1->2->3
int[] list2 = { 8, 4, 2, 1, 4, 1, 1, 7, 6, 7, 7, 6 };
ListNode head2 = createLinkedList(list2);
System.out.print("Before: ");
printLinkedList(head2);
head2 = addOne(head2);
System.out.print("After: ");
printLinkedList(head2);
}
}
```
Unnderstood
thank u bhaiya
Understood
understood
Understood
understood
Understood
understood
Understood
understood
Understood
understood
understood