Runtime Error -addition of unsigned offset

user_13095376 0
Viewed 864

i was solving this problem on leetcode -

Write a function that reverses a string. The input string is given as an array of characters s.

Example 1:

Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Example 2:

Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]

and i wrote this solution which gives a runtime error :addition of unsigned offset

class Solution {
public:
    
    void funToReverse(int left,int right,vector<char> &s){
        if(left==right)
            return;
        else{
            char temp = s[left];
            s[left]=s[right];
            s[right]=temp;
            funToReverse(left+1,right-1,s);
        }
    }
    
    void reverseString(vector<char>& s) {
        int left =0;
        int right = s.size()-1;
        
        
        funToReverse(left,right,s);
    }
};

the error:

Line 1034: Char 34: runtime error: addition of unsigned offset to 0x6020000001b0 overflowed to 0x6020000001af (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

runtime-error function c++ string
1 Answers

The issue is that it's possible for left and right to pass each other without ever being the same value. A way to solve this is:

class Solution {
public:
    
    void funToReverse(int left,int right,vector<char> &s){
        if(left>=right) // Check if left has reached right
            return;
        else{
            char temp = s[left];
            s[left]=s[right];
            s[right]=temp;
            funToReverse(left+1,right-1,s);
        }
    }
    
    void reverseString(vector<char>& s) {
        int left =0;
        int right = s.size()-1;
        
        
        funToReverse(left,right,s);
    }
};

If there is an odd number of elements then (left,right) goes like this: (0, 4), (1, 3), (2, 2)

However, if there is an even number of elements, left will pass right but never be the same: (0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0), (6, -1)

Notice how in this instance, left makes it all the way to 6 and right makes it to -1 which are invalid.

user_105590670
Related