<p>You are given an integer <code>num.</code> <strong>Rearrange</strong> the digits of <code>num</code> such that its value is <strong>minimized</strong> and it does not contain <strong>any</strong> leading zeros.</p>

<p>Return <em>the rearranged number with minimal value</em>.</p>

<p>Note that the sign of the number does not change after rearranging the digits.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = 310
<strong>Output:</strong> 103
<strong>Explanation:</strong> The possible arrangements for the digits of 310 are 013, 031, 103, 130, 301, 310. 
The arrangement with the smallest value that does not contain any leading zeros is 103.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = -7605
<strong>Output:</strong> -7650
<strong>Explanation:</strong> Some possible arrangements for the digits of -7605 are -7650, -6705, -5076, -0567.
The arrangement with the smallest value that does not contain any leading zeros is -7650.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>-10<sup>15</sup> &lt;= num &lt;= 10<sup>15</sup></code></li>
</ul>

class Solution:
    def smallestNumber(self, num: int) -> int:
        def helper(nums):
            if len(nums)<=1:
                return nums
            mid=len(nums)//2
            left=helper(nums[:mid])
            right=helper(nums[mid:])
            return mergeSort(left,right)
        def mergeSort(left,right):
            res=[]
            i=0
            j=0
            while i<len(left) and j<len(right):
                if int(str(left[i])+str(right[j]))<int(str(right[j])+str(left[i])):
                    res.append(left[i])
                    i+=1
                else:
                    res.append(right[j])
                    j+=1
            while i<len(left):
                res.append(left[i])
                i+=1
            while j<len(right):
                res.append(right[j])
                j+=1
            return res

        def helper1(nums):
            if len(nums)<=1:
                return nums
            mid=len(nums)//2
            left=helper1(nums[:mid])
            right=helper1(nums[mid:])
            return mergeSort2(left,right)
        def mergeSort2(left,right):
            res=[]
            i=0
            j=0
            while i<len(left) and j<len(right):
                if int(str(left[i])+str(right[j]))>int(str(right[j])+str(left[i])):
                    res.append(left[i])
                    i+=1
                else:
                    res.append(right[j])
                    j+=1
            while i<len(left):
                res.append(left[i])
                i+=1
            while j<len(right):
                res.append(right[j])
                j+=1
            return res

        nums=[]
        st=str(num)
        if '-' not in st:
            i=0
            zeroCount=0
            for j in st:
                if j=='0':
                    zeroCount+=1
            while i<len(st):
                nm=''
                nm+=st[i]
                temp=i+1
                while temp<len(st) and st[temp]=='0':
                    temp+=1
                i=temp
                nums.append(nm)
            #print(nums)
            ans=helper(nums)
            res=''
            res+=str(ans[0])+'0'*zeroCount
            for i in ans[1::]:
                res+=str(i)
            return int(res)
        else:
            i=1
            while i<len(st):
                nums.append(st[i])
                i+=1
            #print(nums)
            ans=helper1(nums)
            return int('-'+str(int("".join(map(str,ans)))))
        return 0
42