-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0367.swift
70 lines (68 loc) · 1.32 KB
/
q0367.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//
// q0367.swift
// LeetcodeSwift
//
// Created by NowOrNever on 09/05/2020.
// Copyright © 2020 DL. All rights reserved.
//
import Foundation
//367. Valid Perfect Square
//Easy
//
//684
//
//150
//
//Add to List
//
//Share
//Given a positive integer num, write a function which returns True if num is a perfect square else False.
//
//Note: Do not use any built-in library function such as sqrt.
//
//Example 1:
//
//Input: 16
//Output: true
//Example 2:
//
//Input: 14
//Output: false
//Accepted
//164,866
//Submissions
//399,571
class q0367Solution {
func isPerfectSquare(_ num: Int) -> Bool {
var temp = num
var bits = 0
while temp > 0 {
temp >>= 1
bits += 1
}
var upper = 1
for _ in 0..<(bits + 1)/2 {
upper = (upper << 1) + 1
}
var lower = 1
for _ in 0..<(bits - 1) / 2{
lower <<= 1
}
while lower <= upper {
let mid = (lower + upper) / 2
if mid * mid == num {
return true
}else if mid * mid > num {
upper = mid - 1
}else{
lower = mid + 1
}
}
return false
}
}
func q0367(){
let solution = q0367Solution()
let result = solution.isPerfectSquare(16)
print(result)
}