leetcode/javascript/0202-happy-number.js at main · neetcode-gh/leetcode · GitHub

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/**
 * Hash Set - seen dynamic
 * Time O(log(N)) | Space O(log(N))
 * https://leetcode.com/problems/happy-number/
 * @param {number} n
 * @return {boolean}
 */
var isHappy = (n, seen = new Set()) => {
    const hasCycle = () => n === 1 || seen.has(n);
    while (!hasCycle()) {
        /* Time O(log(N)) */
        seen.add(n); /* Space O(log(N)) */
        n = getNext(n); /* Time O(log(N)) */
    }

    return n === 1;
};

var getNext = (n, sum = 0) => {
    while (0 < n) {
        /* Time O(log(N)) */
        const remainder = n % 10;

        n = Math.floor(n / 10);
        sum += remainder * remainder;
    }

    return sum;
};

/**
 * Hash Set - seen static
 * Time O(log(N)) | Space O(1)
 * https://leetcode.com/problems/happy-number/
 * @param {number} n
 * @return {boolean}
 */
var isHappy = (n) => {
    const cycles = [4, 16, 37, 58, 89, 145, 42, 20];
    const seen = new Set(cycles); /* Time O(1)      | Space O(1) */

    const hasCycle = () => n === 1 || seen.has(n);
    while (!hasCycle()) {
        /* Time O(log(N)) | Space O(1) */
        n = getNext(n);
    }

    return n === 1;
};

var getNext = (n, sum = 0) => {
    while (0 < n) {
        /* Time O(log(N)) */
        const remainder = n % 10;

        n = Math.floor(n / 10);
        sum += remainder * remainder;
    }

    return sum;
};

/**
 * Pointer - n === 1 || n === 4
 * Time O(log(N)) | Space O(1)
 * https://leetcode.com/problems/happy-number/
 * @param {number} n
 * @return {boolean}
 */
var isHappy = (n) => {
    const hasCycle = () => n === 1 || n === 4;
    while (!hasCycle()) {
        /* Time O(log(N)) */
        n = getNext(n); /* Time O(log(N)) */
    }

    return n === 1;
};

var getNext = (n, sum = 0) => {
    while (0 < n) {
        /* Time O(log(N)) */
        const remainder = n % 10;

        n = Math.floor(n / 10);
        sum += remainder * remainder;
    }

    return sum;
};

/**
 * Slow Fast
 * Time O(log(N)) | Space O(1)
 * https://leetcode.com/problems/happy-number/
 * @param {number} n
 * @return {boolean}
 */
var isHappy = (n) => {
    let [slow, fast] = [n, getNext(n)];

    const hasCyle = () => fast === 1 || slow === fast;
    while (!hasCyle()) {
        /* Time O(log(N)) */
        slow = getNext(slow); /* Time O(log(N)) */
        fast = getNext(getNext(fast)); /* Time O(log(N)) */
    }

    return fast === 1;
};

var getNext = (n, sum = 0) => {
    while (0 < n) {
        /* Time O(log(N)) */
        const remainder = n % 10;

        n = Math.floor(n / 10);
        sum += remainder * remainder;
    }

    return sum;
};