---
# System prepended metadata

title: 279. Perfect Squares

---

# 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

```
    Example 1:

    Input: n = 12
    Output: 3 
    Explanation: 12 = 4 + 4 + 4.
    Example 2:

    Input: n = 13
    Output: 2
    Explanation: 13 = 4 + 9.
```


### Python Approach
```python=
class Solution:
    def numSquares(self, n: int) -> int:
```


### Java Approach
```Java=
class Solution {
    public int numSquares(int n) {
        /*
            arr[1] = 1
            arr[2] = 2
            arr[3] = 3
            arr[4] = 1 (4)
            arr[5] = 1+1 = 2
            ...
        */
        
        int[] result = new int[n + 1];
        result[0] = 0;
        for(int i = 1; i <= n; i++) {
            result[i] = i;
            for(int j = 1; j*j <= i; j++) {
                result[i] = Math.min(result[i], result[i - j*j] + 1);
            }
        }
        
        /*
          1 -> 1
          2 -> 1
          ...
          4 -> 2 (1, 2) log 4
          ...
          16 -> 4 (1, 2, 3, 4) log16
          
          25 -> 5 [1 - 5] log25 sqrt(25)
          
          n * n^(1/2) = n^(3/2)
         
        */
        
        return result[n];

    }
```



# Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

```
Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
```
```
Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
 ```

Constraints:

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i.

```python=
# O(logN), O(1)
def findPeak(ary):
    n = len(ary)
    l = 0
    r = n - 1
    
    while l <= r:
        mid = l + (r - l) // 2
        # mid : peak
        if (mid == 0 or ary[mid - 1] <= ary[mid]) and (mid == n - 1 or ary[mid] > ary[mid + 1]):
            return mid
        # move l
        elif mid < n - 1 and ary[mid] <= ary[mid + 1]:
            l = mid + 1
        # move r
        elif mid > 0 and ary[mid - 1] > ary[mid]:
            r = mid - 1
    
    return r
```