codingPractice/minimumOperationsToReduceXToZero.js at master · Abhas-Bhatnagar/codingPractice · 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
/**function minSteps(arr, sum,  left, right, direction, hashMap) {
    // console.log(arr, sum,  left, right, direction)
    if (sum == 0) {
        return 0;
    }
    if (left >= arr.length || right < 0) {
        return arr.length+1;
    }

    if (hashMap.hasOwnProperty(sum+"_"+left+"_"+right+"_"+direction)) {
        return hashMap[sum+"_"+left+"_"+right+"_"+direction];
    }

    if (direction == "l") {
        if (sum < arr[left]) {
            return arr.length+1;
        }
        hashMap[sum+"_"+left+"_"+right+"_"+direction] = Math.min(minSteps(arr , sum - arr[left], left + 1 , right , "l" , hashMap) , minSteps(arr , sum - arr[left], left + 1 , right , "r", hashMap)) + 1
    } else {
        if (sum < arr[right]) {
            return arr.length+1;
        }
        hashMap[sum+"_"+left+"_"+right+"_"+direction] =  Math.min(minSteps(arr , sum - arr[right], left , right -1  , "l" , hashMap) , minSteps(arr , sum - arr[right], left , right -1  , "r", hashMap)) + 1
    }
    return hashMap[sum+"_"+left+"_"+right+"_"+direction];
}

var minOperations = function(nums, x) {
    let hashMap = {};

    let minOps = Math.min(minSteps(nums, x , 0, nums.length-1 , "l" , hashMap),    minSteps(nums, x , 0, nums.length-1 , "r" , hashMap));
    return minOps >= nums.length + 1 ? -1 : minOps;
};

let nums = [7060,5935,6241,3627,2117,8471,1689,9098,7227,1660,983,8207,7212,2298,4195,8519,2530,6708,4879,4551,298,6978,8950,4068,9964,9073,9168,3548,8141,8712,6430,2019,628,4306,8794,2949,1702,2595,2237,5137,6146,6462,8360,8766,2999,7117,9094,4788,9484,4491,8711,2167,3334,5269,9235,7641,8334,5018,8802,8964,467,4713,810,7355,3299,6904,6685,5506,767,4712,2601,5577,259,5936,800,732,3239,6671,5911,5495,2572,3054,3455,1614,7818,9594,1273,8298,7586,3509,4241,6913,6706,4866,6507,7924,6874,5835,160,132,5912,7421,4026,9111,4866,3880,5368,1470,9186,5479,1398,1673,7714,5593,7681,803,4139,1583,9852,1465,7040,8031,2134,407,970,8706,8706,6997,7137,6256,827,6155,2347,3348,6063,1128,1531,3343,6225,9081,6414,535,1644,5884,5936,560,9816,3987,5243,9614,2486,118,8890,5847,6853,9263,8318,1978,9487,2784,4992,9527,5081,7848,1129,2006,1297,8127,5534,9545,6971,1954,4376,4243,4360,8394,2171,2885,7152,9175,9099,4477,5771,3195,8677,7429,7083,4204,2513,4262,5906,2635,5350,3433,4430,3583,3685,4666,277,525,9282,531,887,3342,819,4012,5467,4322,743,7643,3346,5384,1535,2559,7501,6655,4441,4421,4227,2432,4269,9703,5177,8668,9406,6441,1062,596,7308,1795,3356,8236,4267,5061,509,9643,5120,9022,3525,4662,7041,9222,3444,2066,407,1497,8394,7745,265,2684,6311,2280,6041,9882,9673,6718,2633,9999,974,322,5563,2493,8311,1707,1687,5261,8731,6833,602,6996,8587,4596,2057,5562,7438,452,8882,2128,573,7149,9863,2210,8010,2727,7282,2082,463,1321,8862,8416,7134,7231,5638,5470,7249,6963,7845,2962,4233,2364,2239,5453,9548,181,5409,8489,8290,3711,6694,1265,8770,4238,5777,9529,7997,7962,641,2551,9516,838,9446,8409,5120,2868,2664,9510,2305,7289,5583,6177,3873,7131,6543,4147,2856,5125,2951,469,4899,4963,4359,628,6331,2619,3171,1491,1246,941,7579,175,2955,4777,7919,2426,807,6827,7516,4908,8629,3980,6566,5974,9957,5811,9203,5811,2994,960,5304,5997,7510,1969,8770,5519,2711,6264,6168,774,3670,8904,4416,2434,634,9988,7457,2254,7844,3797,618,9521,9410,4667,9084,2313,8437,7355,2285,8876,7311,1041,8110,9617,5938,7644,5510,9429,6274,7640,9270,7833,729,1509,9217,3563,7994,432,3968,3347,9916,1451,4227,4662,2563,9069,1287,3311,3978,7977,8706,9380,2612,3438,3848,4146,2599,3563,5113,3254,9937,7588,8947,2367,6612,9102,2268,3556,9617,938,5347,7506,1188,2059,7149,3531,60,9740,4451,2999,1484,5875,1734,8385,2055,613,9496,3694,8493,5400,2016,1997,8022,3527,2435,3231,2114,8440,2885,2925,593,4124,5743,4273,9545,6766,2203,2207,5277,1991,9706,1808,4442,9270,3492,4074,3831,9737,4747,9428,3759,9666,9937,4798,4725,9597,8378,9828,2987,9847,4205,5341,8078,2660,8228,3289,3615,6283,4333,9085,1677,2858,6369,9771,9077,4210,1624,1425,5325,8163,4206,5076,1537,1551,7072,374,3403,3834,3810,856,8635,6627,7111,2235,1414,9601,4879,4895,3111,3487,4630,9179,3899,6823,5165,7337,6516,347,3628,7623,6765,406,3777,4620,4316,5887,8088,345,315,3167,5213,5501,182,9158,1824,4835,4805,8217,9582,454,6990,7231,5864,8081,1407,8904,4580,9540,7968,2029,9003,8917,8207,1950,5121,8921,8149,7299,5471,2822,3513,9376,9424,8479,5654,9873,1779,2690,3599,1073,2809,9584,9780,7598,9516,4936,1193,2145,1223,4069,9454,4079,8637,7142,3161,3072,7699,472,6597,7116,8759,6934,4708,9694,9340,5979,3594,8209,9871,1344,7922,6358,1221,431,350,9000,1471,9448,1702,2773,6257,2488,8586,5677,8458,5171,9624,5974,7273];
let x = 2541008;
console.log(minOperations(nums, x))


*/


function minSteps(arr, sum,  left, right, hashMap) {
    if (sum == 0) {
        return 0;
    }
    if (left >= arr.length || right < 0 || sum < 0 || left > right ) {
        return arr.length+1;
    }

    if (hashMap.hasOwnProperty(sum+"_"+left+"_"+right)) {
        return hashMap[sum+"_"+left+"_"+right];
    }

    hashMap[sum+"_"+left+"_"+right] = Math.min(minSteps(arr , sum - arr[left], left + 1 , right ,hashMap) , minSteps(arr , sum - arr[right], left , right -1  ,hashMap)) + 1

    return hashMap[sum+"_"+left+"_"+right];
}

var minOperations = function(nums, x) {
    let hashMap = {};

    let minOps = minSteps(nums, x , 0, nums.length-1 , hashMap)
    return minOps >= nums.length + 1 ? -1 : minOps;
};

let nums = [7060,5935,6241,3627,2117,8471,1689,9098,7227,1660,983,8207,7212,2298,4195,8519,2530,6708,4879,4551,298,6978,8950,4068,9964,9073,9168,3548,8141,8712,6430,2019,628,4306,8794,2949,1702,2595,2237,5137,6146,6462,8360,8766,2999,7117,9094,4788,9484,4491,8711,2167,3334,5269,9235,7641,8334,5018,8802,8964,467,4713,810,7355,3299,6904,6685,5506,767,4712,2601,5577,259,5936,800,732,3239,6671,5911,5495,2572,3054,3455,1614,7818,9594,1273,8298,7586,3509,4241,6913,6706,4866,6507,7924,6874,5835,160,132,5912,7421,4026,9111,4866,3880,5368,1470,9186,5479,1398,1673,7714,5593,7681,803,4139,1583,9852,1465,7040,8031,2134,407,970,8706,8706,6997,7137,6256,827,6155,2347,3348,6063,1128,1531,3343,6225,9081,6414,535,1644,5884,5936,560,9816,3987,5243,9614,2486,118,8890,5847,6853,9263,8318,1978,9487,2784,4992,9527,5081,7848,1129,2006,1297,8127,5534,9545,6971,1954,4376,4243,4360,8394,2171,2885,7152,9175,9099,4477,5771,3195,8677,7429,7083,4204,2513,4262,5906,2635,5350,3433,4430,3583,3685,4666,277,525,9282,531,887,3342,819,4012,5467,4322,743,7643,3346,5384,1535,2559,7501,6655,4441,4421,4227,2432,4269,9703,5177,8668,9406,6441,1062,596,7308,1795,3356,8236,4267,5061,509,9643,5120,9022,3525,4662,7041,9222,3444,2066,407,1497,8394,7745,265,2684,6311,2280,6041,9882,9673,6718,2633,9999,974,322,5563,2493,8311,1707,1687,5261,8731,6833,602,6996,8587,4596,2057,5562,7438,452,8882,2128,573,7149,9863,2210,8010,2727,7282,2082,463,1321,8862,8416,7134,7231,5638,5470,7249,6963,7845,2962,4233,2364,2239,5453,9548,181,5409,8489,8290,3711,6694,1265,8770,4238,5777,9529,7997,7962,641,2551,9516,838,9446,8409,5120,2868,2664,9510,2305,7289,5583,6177,3873,7131,6543,4147,2856,5125,2951,469,4899,4963,4359,628,6331,2619,3171,1491,1246,941,7579,175,2955,4777,7919,2426,807,6827,7516,4908,8629,3980,6566,5974,9957,5811,9203,5811,2994,960,5304,5997,7510,1969,8770,5519,2711,6264,6168,774,3670,8904,4416,2434,634,9988,7457,2254,7844,3797,618,9521,9410,4667,9084,2313,8437,7355,2285,8876,7311,1041,8110,9617,5938,7644,5510,9429,6274,7640,9270,7833,729,1509,9217,3563,7994,432,3968,3347,9916,1451,4227,4662,2563,9069,1287,3311,3978,7977,8706,9380,2612,3438,3848,4146,2599,3563,5113,3254,9937,7588,8947,2367,6612,9102,2268,3556,9617,938,5347,7506,1188,2059,7149,3531,60,9740,4451,2999,1484,5875,1734,8385,2055,613,9496,3694,8493,5400,2016,1997,8022,3527,2435,3231,2114,8440,2885,2925,593,4124,5743,4273,9545,6766,2203,2207,5277,1991,9706,1808,4442,9270,3492,4074,3831,9737,4747,9428,3759,9666,9937,4798,4725,9597,8378,9828,2987,9847,4205,5341,8078,2660,8228,3289,3615,6283,4333,9085,1677,2858,6369,9771,9077,4210,1624,1425,5325,8163,4206,5076,1537,1551,7072,374,3403,3834,3810,856,8635,6627,7111,2235,1414,9601,4879,4895,3111,3487,4630,9179,3899,6823,5165,7337,6516,347,3628,7623,6765,406,3777,4620,4316,5887,8088,345,315,3167,5213,5501,182,9158,1824,4835,4805,8217,9582,454,6990,7231,5864,8081,1407,8904,4580,9540,7968,2029,9003,8917,8207,1950,5121,8921,8149,7299,5471,2822,3513,9376,9424,8479,5654,9873,1779,2690,3599,1073,2809,9584,9780,7598,9516,4936,1193,2145,1223,4069,9454,4079,8637,7142,3161,3072,7699,472,6597,7116,8759,6934,4708,9694,9340,5979,3594,8209,9871,1344,7922,6358,1221,431,350,9000,1471,9448,1702,2773,6257,2488,8586,5677,8458,5171,9624,5974,7273];
let x = 2541008;
console.log(minOperations(nums, x))