2601. Prime Subtraction Operation

2601. Prime Subtraction Operation
Solved
Medium
Topics
Companies
Hint
You are given a 0-indexed integer array nums of length n.

You can perform the following operation as many times as you want:

Pick an index i that you haven’t picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i].
Return true if you can make nums a strictly increasing array using the above operation and false otherwise.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

---

접근

 

주어진 숫자 배열이 오름차순을 이루도록 자신의 숫자를 소수 ( prime number ) 로 빼는 작업을 수행합니다.

위 과정으로 오름차순이 만들어지면 성공합니다.

오름차순을 이루기 위해서는 Index 기준 오른쪽의 값이 자신의 값보다 커야하므로, 주어진 배열의 가장 마지막 값으로부터 왼쪽으로 순회하면서 오른쪽 값보다 작아지는 소수를 찾습니다.

이는 'i' 번째 기준으로 'i + 1' 의 값과의 차이 ( min ) 와 'i' 번쨰 값 ( max ) 사이의 소수 ( prime ) 가 존재하는 지 검사합니다.

소수는 미리 계산할 수 있으므로 배열로 준비합니다.

* 문제에서 주어지는 element 의 값은 1000 보다 작으므로 1000 까지의 소수 값을 준비합니다

** 범위 안의 소수를 얻는 방법으로 'sieve of eratoshness' 를 사용할 수 있습니다

---

코드

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var primeSubOperation = function (nums) {
    var len = nums.length;

    if (len == 1) return true;

    // (p) : 1 <= nums[i] <= 1000
    // Sieve of Eratosthenes
    var ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
        , 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199
        , 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293
        , 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397
        , 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499
        , 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599
        , 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691
        , 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797
        , 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887
        , 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009];

    // ex) [2,3,4]
    for (var i = len - 2; i >= 0; i--) {
        var com = nums[i + 1];
        var cur = nums[i];

        if (com == 1) return false;

        if (cur >= com) {
            var min = cur - com;
            var max = cur;

            for (var j = 0; j < ps.length; j++) {
                var p = ps[j];

                if (p >= max) return false;

                if (min < p) {
                    nums[i] -= p;
                    break;
                }
            }
        }
    }

    return true;
};