---
# System prepended metadata

title: Path Sum III

---

# Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

### Example:

```
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
```


### code
```
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        mem = {}
        def dfs(root, num):
            res = 0
            if not root:
                return res
                
            # if hit cache
            if root in mem and num in mem[root]:
                return mem[root][num]
            
            if root.val == num:
                res += 1
            res += dfs(root.left, num - root.val)
            res += dfs(root.right, num - root.val)
            
            # update mem cache
            if root in mem:
                mem[root][num] = res
            else:
               mem[root] = {}
               mem[root][num] = res
            
            return mem[root][num]
    
        if not root:
            return 0
        out = dfs(root, sum)
        out += pathSum(root.left, sum)
        out += pathSum(root.right, sum)
        
        return out
```



<br>


## An

Implement pow(x, n), which calculates x raised to the power n (i.e. xn).


### Example 1:
```
Input: x = 2.00000, n = 10
Output: 1024.00000
```
### Example 2:

```
Input: x = 2.10000, n = 3
Output: 9.26100
```

### Example 3:

```
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
```

### Constraints:

```
-100.0 < x < 100.0
-2^31 <= n <= 2^31 -1
-10^4 <= x^n <= 10^4
```

### Approach:
```
public double pow(double x, int n) {
    // when n < 0
    long N = n;
    if(N < 0) {
        N = -N; //positive
        x = 1.00/x;
    }
    
    // init ans
    // init product of digit
    double ans = 1.00;
    double pd = x;
    
    
    for(long i = N; i > 0; i /= 2) {
        if(i % 2 != 0) {
            ans = ans * pd; // ans *= pd
        }
        pd = pd * pd;  // pd *= pd
    }

    // return
    return ans;
}

```
x*x*x*....  (N times)

(x*x)
(x*x)*(x*x)
((x*x)*(x*x))*((x*x)*(xx))

Time Complexity
O(log(N))
Space Complexity 
O(1)

### Code:
```python:
class Solution:
    def myPow(self, x: float, n: int) -> float:
        # corner cases
        if x in [float(0), float(1)]:
            return x
        # n < 0 cases:
        if n < 0:
            x, n = 1/x, abs(n)
        
        res = 1
        while n > 0:
            # key: odd case
            if n % 2 == 1:
                res *= x
            x *= x
            n >>= 1
        
        return res

```




