LeetCode Improvisation Technique
The solution to this problem required a little improvisation technique, which some might say it is "cheating" but that's very subjective.
The problem is this one, take a look: https://leetcode.com/problems/2-keys-keyboard/description/
The solution I came up with was a breadth-first-search (BFS) where the transitions (copy or paste) are the enqueueing steps. So far so good, but unfortunately the code timed out towards the very last steps. Here is the improvisation though: the input asked was from 1..1000. Now that's tiny. What I could do then was using the BFS code (which actually runs relatively fast) pre-compute all answers from 1..1000, create a hashtable with all the answers, and simply index the hashtable. Hence, the first solution, although workable, did not make the cut, whereas the second one did. Both solutions below. Cheers, Marcelo.
Solution 1 (BFS, times out, but works):
public class Solution
{
public int MinSteps(int n)
{
Queue queue = new Queue();
Hashtable alreadySeen = new Hashtable();
EnqueueItem ei = new EnqueueItem("A", "", 0, null);
alreadySeen.Add(ei.current + "@" + ei.paste, true);
queue.Enqueue(ei);
while (queue.Count > 0)
{
EnqueueItem currentItem = (EnqueueItem)queue.Dequeue();
if (currentItem.current.Length == n)
{
//PrintBacktrack(currentItem);
return currentItem.numberSteps;
}
//Copy
if (currentItem.current.Length <= n && currentItem.paste.Length > 0 && !alreadySeen.ContainsKey(currentItem.current + currentItem.paste + "@" + currentItem.paste))
{
EnqueueItem currentItemCopy = new EnqueueItem(currentItem.current + currentItem.paste, currentItem.paste, currentItem.numberSteps + 1, currentItem);
alreadySeen.Add(currentItem.current + currentItem.paste + "@" + currentItem.paste, true);
queue.Enqueue(currentItemCopy);
}
//Paste
if (currentItem.current.Length <= n && !alreadySeen.ContainsKey(currentItem.current + "@" + currentItem.current))
{
EnqueueItem currentItemPaste = new EnqueueItem(currentItem.current, currentItem.current, currentItem.numberSteps + 1, currentItem);
alreadySeen.Add(currentItem.current + "@" + currentItem.current, true);
queue.Enqueue(currentItemPaste);
}
}
return -1;
}
private void PrintBacktrack(EnqueueItem ei)
{
if (ei.from != null) PrintBacktrack(ei.from);
if (ei.from == null) return;
if (ei.current == ei.paste) Console.WriteLine("Step {0}: pasted '{1}' to the clipboard. Current: {2}. Clipboard = {3}", ei.numberSteps, ei.current, ei.current, ei.paste);
else Console.WriteLine("Step {0}: copied '{1}' from the clipboard. Current: {2}. Clipboard = {3}", ei.numberSteps, ei.paste, ei.current, ei.paste);
}
private class EnqueueItem
{
public string current = "";
public string paste = "";
public int numberSteps = 0;
public EnqueueItem from = null;
public EnqueueItem(string current,
string paste,
int numberSteps,
EnqueueItem from)
{
this.current = current;
this.paste = paste;
this.numberSteps = numberSteps;
if (from != null)
{
this.from = new EnqueueItem(from.current, from.paste, from.numberSteps, from.from);
}
}
}
}
Solution 2 (indexation based on solution 1, works fast):
public class Solution {
private Hashtable ht = null;
public Solution()
{
ht = new Hashtable();
ht.Add(1, 0);
ht.Add(2, 2);
ht.Add(3, 3);
ht.Add(4, 4);
ht.Add(5, 5);
ht.Add(6, 5);
ht.Add(7, 7);
ht.Add(8, 6);
ht.Add(9, 6);
ht.Add(10, 7);
ht.Add(11, 11);
ht.Add(12, 7);
ht.Add(13, 13);
ht.Add(14, 9);
ht.Add(15, 8);
ht.Add(16, 8);
ht.Add(17, 17);
ht.Add(18, 8);
ht.Add(19, 19);
ht.Add(20, 9);
ht.Add(21, 10);
ht.Add(22, 13);
ht.Add(23, 23);
ht.Add(24, 9);
ht.Add(25, 10);
ht.Add(26, 15);
ht.Add(27, 9);
ht.Add(28, 11);
ht.Add(29, 29);
ht.Add(30, 10);
ht.Add(31, 31);
ht.Add(32, 10);
ht.Add(33, 14);
ht.Add(34, 19);
ht.Add(35, 12);
ht.Add(36, 10);
ht.Add(37, 37);
ht.Add(38, 21);
ht.Add(39, 16);
ht.Add(40, 11);
ht.Add(41, 41);
ht.Add(42, 12);
ht.Add(43, 43);
ht.Add(44, 15);
ht.Add(45, 11);
ht.Add(46, 25);
ht.Add(47, 47);
ht.Add(48, 11);
ht.Add(49, 14);
ht.Add(50, 12);
ht.Add(51, 20);
ht.Add(52, 17);
ht.Add(53, 53);
ht.Add(54, 11);
ht.Add(55, 16);
ht.Add(56, 13);
ht.Add(57, 22);
ht.Add(58, 31);
ht.Add(59, 59);
ht.Add(60, 12);
ht.Add(61, 61);
ht.Add(62, 33);
ht.Add(63, 13);
ht.Add(64, 12);
ht.Add(65, 18);
ht.Add(66, 16);
ht.Add(67, 67);
ht.Add(68, 21);
ht.Add(69, 26);
ht.Add(70, 14);
ht.Add(71, 71);
ht.Add(72, 12);
ht.Add(73, 73);
ht.Add(74, 39);
ht.Add(75, 13);
ht.Add(76, 23);
ht.Add(77, 18);
ht.Add(78, 18);
ht.Add(79, 79);
ht.Add(80, 13);
ht.Add(81, 12);
ht.Add(82, 43);
ht.Add(83, 83);
ht.Add(84, 14);
ht.Add(85, 22);
ht.Add(86, 45);
ht.Add(87, 32);
ht.Add(88, 17);
ht.Add(89, 89);
ht.Add(90, 13);
ht.Add(91, 20);
ht.Add(92, 27);
ht.Add(93, 34);
ht.Add(94, 49);
ht.Add(95, 24);
ht.Add(96, 13);
ht.Add(97, 97);
ht.Add(98, 16);
ht.Add(99, 17);
ht.Add(100, 14);
ht.Add(101, 101);
ht.Add(102, 22);
ht.Add(103, 103);
ht.Add(104, 19);
ht.Add(105, 15);
ht.Add(106, 55);
ht.Add(107, 107);
ht.Add(108, 13);
ht.Add(109, 109);
ht.Add(110, 18);
ht.Add(111, 40);
ht.Add(112, 15);
ht.Add(113, 113);
ht.Add(114, 24);
ht.Add(115, 28);
ht.Add(116, 33);
ht.Add(117, 19);
ht.Add(118, 61);
ht.Add(119, 24);
ht.Add(120, 14);
ht.Add(121, 22);
ht.Add(122, 63);
ht.Add(123, 44);
ht.Add(124, 35);
ht.Add(125, 15);
ht.Add(126, 15);
ht.Add(127, 127);
ht.Add(128, 14);
ht.Add(129, 46);
ht.Add(130, 20);
ht.Add(131, 131);
ht.Add(132, 18);
ht.Add(133, 26);
ht.Add(134, 69);
ht.Add(135, 14);
ht.Add(136, 23);
ht.Add(137, 137);
ht.Add(138, 28);
ht.Add(139, 139);
ht.Add(140, 16);
ht.Add(141, 50);
ht.Add(142, 73);
ht.Add(143, 24);
ht.Add(144, 14);
ht.Add(145, 34);
ht.Add(146, 75);
ht.Add(147, 17);
ht.Add(148, 41);
ht.Add(149, 149);
ht.Add(150, 15);
ht.Add(151, 151);
ht.Add(152, 25);
ht.Add(153, 23);
ht.Add(154, 20);
ht.Add(155, 36);
ht.Add(156, 20);
ht.Add(157, 157);
ht.Add(158, 81);
ht.Add(159, 56);
ht.Add(160, 15);
ht.Add(161, 30);
ht.Add(162, 14);
ht.Add(163, 163);
ht.Add(164, 45);
ht.Add(165, 19);
ht.Add(166, 85);
ht.Add(167, 167);
ht.Add(168, 16);
ht.Add(169, 26);
ht.Add(170, 24);
ht.Add(171, 25);
ht.Add(172, 47);
ht.Add(173, 173);
ht.Add(174, 34);
ht.Add(175, 17);
ht.Add(176, 19);
ht.Add(177, 62);
ht.Add(178, 91);
ht.Add(179, 179);
ht.Add(180, 15);
ht.Add(181, 181);
ht.Add(182, 22);
ht.Add(183, 64);
ht.Add(184, 29);
ht.Add(185, 42);
ht.Add(186, 36);
ht.Add(187, 28);
ht.Add(188, 51);
ht.Add(189, 16);
ht.Add(190, 26);
ht.Add(191, 191);
ht.Add(192, 15);
ht.Add(193, 193);
ht.Add(194, 99);
ht.Add(195, 21);
ht.Add(196, 18);
ht.Add(197, 197);
ht.Add(198, 19);
ht.Add(199, 199);
ht.Add(200, 16);
ht.Add(201, 70);
ht.Add(202, 103);
ht.Add(203, 36);
ht.Add(204, 24);
ht.Add(205, 46);
ht.Add(206, 105);
ht.Add(207, 29);
ht.Add(208, 21);
ht.Add(209, 30);
ht.Add(210, 17);
ht.Add(211, 211);
ht.Add(212, 57);
ht.Add(213, 74);
ht.Add(214, 109);
ht.Add(215, 48);
ht.Add(216, 15);
ht.Add(217, 38);
ht.Add(218, 111);
ht.Add(219, 76);
ht.Add(220, 20);
ht.Add(221, 30);
ht.Add(222, 42);
ht.Add(223, 223);
ht.Add(224, 17);
ht.Add(225, 16);
ht.Add(226, 115);
ht.Add(227, 227);
ht.Add(228, 26);
ht.Add(229, 229);
ht.Add(230, 30);
ht.Add(231, 21);
ht.Add(232, 35);
ht.Add(233, 233);
ht.Add(234, 21);
ht.Add(235, 52);
ht.Add(236, 63);
ht.Add(237, 82);
ht.Add(238, 26);
ht.Add(239, 239);
ht.Add(240, 16);
ht.Add(241, 241);
ht.Add(242, 24);
ht.Add(243, 15);
ht.Add(244, 65);
ht.Add(245, 19);
ht.Add(246, 46);
ht.Add(247, 32);
ht.Add(248, 37);
ht.Add(249, 86);
ht.Add(250, 17);
ht.Add(251, 251);
ht.Add(252, 17);
ht.Add(253, 34);
ht.Add(254, 129);
ht.Add(255, 25);
ht.Add(256, 16);
ht.Add(257, 257);
ht.Add(258, 48);
ht.Add(259, 44);
ht.Add(260, 22);
ht.Add(261, 35);
ht.Add(262, 133);
ht.Add(263, 263);
ht.Add(264, 20);
ht.Add(265, 58);
ht.Add(266, 28);
ht.Add(267, 92);
ht.Add(268, 71);
ht.Add(269, 269);
ht.Add(270, 16);
ht.Add(271, 271);
ht.Add(272, 25);
ht.Add(273, 23);
ht.Add(274, 139);
ht.Add(275, 21);
ht.Add(276, 30);
ht.Add(277, 277);
ht.Add(278, 141);
ht.Add(279, 37);
ht.Add(280, 18);
ht.Add(281, 281);
ht.Add(282, 52);
ht.Add(283, 283);
ht.Add(284, 75);
ht.Add(285, 27);
ht.Add(286, 26);
ht.Add(287, 48);
ht.Add(288, 16);
ht.Add(289, 34);
ht.Add(290, 36);
ht.Add(291, 100);
ht.Add(292, 77);
ht.Add(293, 293);
ht.Add(294, 19);
ht.Add(295, 64);
ht.Add(296, 43);
ht.Add(297, 20);
ht.Add(298, 151);
ht.Add(299, 36);
ht.Add(300, 17);
ht.Add(301, 50);
ht.Add(302, 153);
ht.Add(303, 104);
ht.Add(304, 27);
ht.Add(305, 66);
ht.Add(306, 25);
ht.Add(307, 307);
ht.Add(308, 22);
ht.Add(309, 106);
ht.Add(310, 38);
ht.Add(311, 311);
ht.Add(312, 22);
ht.Add(313, 313);
ht.Add(314, 159);
ht.Add(315, 18);
ht.Add(316, 83);
ht.Add(317, 317);
ht.Add(318, 58);
ht.Add(319, 40);
ht.Add(320, 17);
ht.Add(321, 110);
ht.Add(322, 32);
ht.Add(323, 36);
ht.Add(324, 16);
ht.Add(325, 23);
ht.Add(326, 165);
ht.Add(327, 112);
ht.Add(328, 47);
ht.Add(329, 54);
ht.Add(330, 21);
ht.Add(331, 331);
ht.Add(332, 87);
ht.Add(333, 43);
ht.Add(334, 169);
ht.Add(335, 72);
ht.Add(336, 18);
ht.Add(337, 337);
ht.Add(338, 28);
ht.Add(339, 116);
ht.Add(340, 26);
ht.Add(341, 42);
ht.Add(342, 27);
ht.Add(343, 21);
ht.Add(344, 49);
ht.Add(345, 31);
ht.Add(346, 175);
ht.Add(347, 347);
ht.Add(348, 36);
ht.Add(349, 349);
ht.Add(350, 19);
ht.Add(351, 22);
ht.Add(352, 21);
ht.Add(353, 353);
ht.Add(354, 64);
ht.Add(355, 76);
ht.Add(356, 93);
ht.Add(357, 27);
ht.Add(358, 181);
ht.Add(359, 359);
ht.Add(360, 17);
ht.Add(361, 38);
ht.Add(362, 183);
ht.Add(363, 25);
ht.Add(364, 24);
ht.Add(365, 78);
ht.Add(366, 66);
ht.Add(367, 367);
ht.Add(368, 31);
ht.Add(369, 47);
ht.Add(370, 44);
ht.Add(371, 60);
ht.Add(372, 38);
ht.Add(373, 373);
ht.Add(374, 30);
ht.Add(375, 18);
ht.Add(376, 53);
ht.Add(377, 42);
ht.Add(378, 18);
ht.Add(379, 379);
ht.Add(380, 28);
ht.Add(381, 130);
ht.Add(382, 193);
ht.Add(383, 383);
ht.Add(384, 17);
ht.Add(385, 23);
ht.Add(386, 195);
ht.Add(387, 49);
ht.Add(388, 101);
ht.Add(389, 389);
ht.Add(390, 23);
ht.Add(391, 40);
ht.Add(392, 20);
ht.Add(393, 134);
ht.Add(394, 199);
ht.Add(395, 84);
ht.Add(396, 21);
ht.Add(397, 397);
ht.Add(398, 201);
ht.Add(399, 29);
ht.Add(400, 18);
ht.Add(401, 401);
ht.Add(402, 72);
ht.Add(403, 44);
ht.Add(404, 105);
ht.Add(405, 17);
ht.Add(406, 38);
ht.Add(407, 48);
ht.Add(408, 26);
ht.Add(409, 409);
ht.Add(410, 48);
ht.Add(411, 140);
ht.Add(412, 107);
ht.Add(413, 66);
ht.Add(414, 31);
ht.Add(415, 88);
ht.Add(416, 23);
ht.Add(417, 142);
ht.Add(418, 32);
ht.Add(419, 419);
ht.Add(420, 19);
ht.Add(421, 421);
ht.Add(422, 213);
ht.Add(423, 53);
ht.Add(424, 59);
ht.Add(425, 27);
ht.Add(426, 76);
ht.Add(427, 68);
ht.Add(428, 111);
ht.Add(429, 27);
ht.Add(430, 50);
ht.Add(431, 431);
ht.Add(432, 17);
ht.Add(433, 433);
ht.Add(434, 40);
ht.Add(435, 37);
ht.Add(436, 113);
ht.Add(437, 42);
ht.Add(438, 78);
ht.Add(439, 439);
ht.Add(440, 22);
ht.Add(441, 20);
ht.Add(442, 32);
ht.Add(443, 443);
ht.Add(444, 44);
ht.Add(445, 94);
ht.Add(446, 225);
ht.Add(447, 152);
ht.Add(448, 19);
ht.Add(449, 449);
ht.Add(450, 18);
ht.Add(451, 52);
ht.Add(452, 117);
ht.Add(453, 154);
ht.Add(454, 229);
ht.Add(455, 25);
ht.Add(456, 28);
ht.Add(457, 457);
ht.Add(458, 231);
ht.Add(459, 26);
ht.Add(460, 32);
ht.Add(461, 461);
ht.Add(462, 23);
ht.Add(463, 463);
ht.Add(464, 37);
ht.Add(465, 39);
ht.Add(466, 235);
ht.Add(467, 467);
ht.Add(468, 23);
ht.Add(469, 74);
ht.Add(470, 54);
ht.Add(471, 160);
ht.Add(472, 65);
ht.Add(473, 54);
ht.Add(474, 84);
ht.Add(475, 29);
ht.Add(476, 28);
ht.Add(477, 59);
ht.Add(478, 241);
ht.Add(479, 479);
ht.Add(480, 18);
ht.Add(481, 50);
ht.Add(482, 243);
ht.Add(483, 33);
ht.Add(484, 26);
ht.Add(485, 102);
ht.Add(486, 17);
ht.Add(487, 487);
ht.Add(488, 67);
ht.Add(489, 166);
ht.Add(490, 21);
ht.Add(491, 491);
ht.Add(492, 48);
ht.Add(493, 46);
ht.Add(494, 34);
ht.Add(495, 22);
ht.Add(496, 39);
ht.Add(497, 78);
ht.Add(498, 88);
ht.Add(499, 499);
ht.Add(500, 19);
ht.Add(501, 170);
ht.Add(502, 253);
ht.Add(503, 503);
ht.Add(504, 19);
ht.Add(505, 106);
ht.Add(506, 36);
ht.Add(507, 29);
ht.Add(508, 131);
ht.Add(509, 509);
ht.Add(510, 27);
ht.Add(511, 80);
ht.Add(512, 18);
ht.Add(513, 28);
ht.Add(514, 259);
ht.Add(515, 108);
ht.Add(516, 50);
ht.Add(517, 58);
ht.Add(518, 46);
ht.Add(519, 176);
ht.Add(520, 24);
ht.Add(521, 521);
ht.Add(522, 37);
ht.Add(523, 523);
ht.Add(524, 135);
ht.Add(525, 20);
ht.Add(526, 265);
ht.Add(527, 48);
ht.Add(528, 22);
ht.Add(529, 46);
ht.Add(530, 60);
ht.Add(531, 65);
ht.Add(532, 30);
ht.Add(533, 54);
ht.Add(534, 94);
ht.Add(535, 112);
ht.Add(536, 73);
ht.Add(537, 182);
ht.Add(538, 271);
ht.Add(539, 25);
ht.Add(540, 18);
ht.Add(541, 541);
ht.Add(542, 273);
ht.Add(543, 184);
ht.Add(544, 27);
ht.Add(545, 114);
ht.Add(546, 25);
ht.Add(547, 547);
ht.Add(548, 141);
ht.Add(549, 67);
ht.Add(550, 23);
ht.Add(551, 48);
ht.Add(552, 32);
ht.Add(553, 86);
ht.Add(554, 279);
ht.Add(555, 45);
ht.Add(556, 143);
ht.Add(557, 557);
ht.Add(558, 39);
ht.Add(559, 56);
ht.Add(560, 20);
ht.Add(561, 31);
ht.Add(562, 283);
ht.Add(563, 563);
ht.Add(564, 54);
ht.Add(565, 118);
ht.Add(566, 285);
ht.Add(567, 19);
ht.Add(568, 77);
ht.Add(569, 569);
ht.Add(570, 29);
ht.Add(571, 571);
ht.Add(572, 28);
ht.Add(573, 194);
ht.Add(574, 50);
ht.Add(575, 33);
ht.Add(576, 18);
ht.Add(577, 577);
ht.Add(578, 36);
ht.Add(579, 196);
ht.Add(580, 38);
ht.Add(581, 90);
ht.Add(582, 102);
ht.Add(583, 64);
ht.Add(584, 79);
ht.Add(585, 24);
ht.Add(586, 295);
ht.Add(587, 587);
ht.Add(588, 21);
ht.Add(589, 50);
ht.Add(590, 66);
ht.Add(591, 200);
ht.Add(592, 45);
ht.Add(593, 593);
ht.Add(594, 22);
ht.Add(595, 29);
ht.Add(596, 153);
ht.Add(597, 202);
ht.Add(598, 38);
ht.Add(599, 599);
ht.Add(600, 19);
ht.Add(601, 601);
ht.Add(602, 52);
ht.Add(603, 73);
ht.Add(604, 155);
ht.Add(605, 27);
ht.Add(606, 106);
ht.Add(607, 607);
ht.Add(608, 29);
ht.Add(609, 39);
ht.Add(610, 68);
ht.Add(611, 60);
ht.Add(612, 27);
ht.Add(613, 613);
ht.Add(614, 309);
ht.Add(615, 49);
ht.Add(616, 24);
ht.Add(617, 617);
ht.Add(618, 108);
ht.Add(619, 619);
ht.Add(620, 40);
ht.Add(621, 32);
ht.Add(622, 313);
ht.Add(623, 96);
ht.Add(624, 24);
ht.Add(625, 20);
ht.Add(626, 315);
ht.Add(627, 33);
ht.Add(628, 161);
ht.Add(629, 54);
ht.Add(630, 20);
ht.Add(631, 631);
ht.Add(632, 85);
ht.Add(633, 214);
ht.Add(634, 319);
ht.Add(635, 132);
ht.Add(636, 60);
ht.Add(637, 27);
ht.Add(638, 42);
ht.Add(639, 77);
ht.Add(640, 19);
ht.Add(641, 641);
ht.Add(642, 112);
ht.Add(643, 643);
ht.Add(644, 34);
ht.Add(645, 51);
ht.Add(646, 38);
ht.Add(647, 647);
ht.Add(648, 18);
ht.Add(649, 70);
ht.Add(650, 25);
ht.Add(651, 41);
ht.Add(652, 167);
ht.Add(653, 653);
ht.Add(654, 114);
ht.Add(655, 136);
ht.Add(656, 49);
ht.Add(657, 79);
ht.Add(658, 56);
ht.Add(659, 659);
ht.Add(660, 23);
ht.Add(661, 661);
ht.Add(662, 333);
ht.Add(663, 33);
ht.Add(664, 89);
ht.Add(665, 31);
ht.Add(666, 45);
ht.Add(667, 52);
ht.Add(668, 171);
ht.Add(669, 226);
ht.Add(670, 74);
ht.Add(671, 72);
ht.Add(672, 20);
ht.Add(673, 673);
ht.Add(674, 339);
ht.Add(675, 19);
ht.Add(676, 30);
ht.Add(677, 677);
ht.Add(678, 118);
ht.Add(679, 104);
ht.Add(680, 28);
ht.Add(681, 230);
ht.Add(682, 44);
ht.Add(683, 683);
ht.Add(684, 29);
ht.Add(685, 142);
ht.Add(686, 23);
ht.Add(687, 232);
ht.Add(688, 51);
ht.Add(689, 66);
ht.Add(690, 33);
ht.Add(691, 691);
ht.Add(692, 177);
ht.Add(693, 24);
ht.Add(694, 349);
ht.Add(695, 144);
ht.Add(696, 38);
ht.Add(697, 58);
ht.Add(698, 351);
ht.Add(699, 236);
ht.Add(700, 21);
ht.Add(701, 701);
ht.Add(702, 24);
ht.Add(703, 56);
ht.Add(704, 23);
ht.Add(705, 55);
ht.Add(706, 355);
ht.Add(707, 108);
ht.Add(708, 66);
ht.Add(709, 709);
ht.Add(710, 78);
ht.Add(711, 85);
ht.Add(712, 95);
ht.Add(713, 54);
ht.Add(714, 29);
ht.Add(715, 29);
ht.Add(716, 183);
ht.Add(717, 242);
ht.Add(718, 361);
ht.Add(719, 719);
ht.Add(720, 19);
ht.Add(721, 110);
ht.Add(722, 40);
ht.Add(723, 244);
ht.Add(724, 185);
ht.Add(725, 39);
ht.Add(726, 27);
ht.Add(727, 727);
ht.Add(728, 26);
ht.Add(729, 18);
ht.Add(730, 80);
ht.Add(731, 60);
ht.Add(732, 68);
ht.Add(733, 733);
ht.Add(734, 369);
ht.Add(735, 22);
ht.Add(736, 33);
ht.Add(737, 78);
ht.Add(738, 49);
ht.Add(739, 739);
ht.Add(740, 46);
ht.Add(741, 35);
ht.Add(742, 62);
ht.Add(743, 743);
ht.Add(744, 40);
ht.Add(745, 154);
ht.Add(746, 375);
ht.Add(747, 89);
ht.Add(748, 32);
ht.Add(749, 114);
ht.Add(750, 20);
ht.Add(751, 751);
ht.Add(752, 55);
ht.Add(753, 254);
ht.Add(754, 44);
ht.Add(755, 156);
ht.Add(756, 20);
ht.Add(757, 757);
ht.Add(758, 381);
ht.Add(759, 37);
ht.Add(760, 30);
ht.Add(761, 761);
ht.Add(762, 132);
ht.Add(763, 116);
ht.Add(764, 195);
ht.Add(765, 28);
ht.Add(766, 385);
ht.Add(767, 72);
ht.Add(768, 19);
ht.Add(769, 769);
ht.Add(770, 25);
ht.Add(771, 260);
ht.Add(772, 197);
ht.Add(773, 773);
ht.Add(774, 51);
ht.Add(775, 41);
ht.Add(776, 103);
ht.Add(777, 47);
ht.Add(778, 391);
ht.Add(779, 60);
ht.Add(780, 25);
ht.Add(781, 82);
ht.Add(782, 42);
ht.Add(783, 38);
ht.Add(784, 22);
ht.Add(785, 162);
ht.Add(786, 136);
ht.Add(787, 787);
ht.Add(788, 201);
ht.Add(789, 266);
ht.Add(790, 86);
ht.Add(791, 120);
ht.Add(792, 23);
ht.Add(793, 74);
ht.Add(794, 399);
ht.Add(795, 61);
ht.Add(796, 203);
ht.Add(797, 797);
ht.Add(798, 31);
ht.Add(799, 64);
ht.Add(800, 20);
ht.Add(801, 95);
ht.Add(802, 403);
ht.Add(803, 84);
ht.Add(804, 74);
ht.Add(805, 35);
ht.Add(806, 46);
ht.Add(807, 272);
ht.Add(808, 107);
ht.Add(809, 809);
ht.Add(810, 19);
ht.Add(811, 811);
ht.Add(812, 40);
ht.Add(813, 274);
ht.Add(814, 50);
ht.Add(815, 168);
ht.Add(816, 28);
ht.Add(817, 62);
ht.Add(818, 411);
ht.Add(819, 26);
ht.Add(820, 50);
ht.Add(821, 821);
ht.Add(822, 142);
ht.Add(823, 823);
ht.Add(824, 109);
ht.Add(825, 24);
ht.Add(826, 68);
ht.Add(827, 827);
ht.Add(828, 33);
ht.Add(829, 829);
ht.Add(830, 90);
ht.Add(831, 280);
ht.Add(832, 25);
ht.Add(833, 31);
ht.Add(834, 144);
ht.Add(835, 172);
ht.Add(836, 34);
ht.Add(837, 40);
ht.Add(838, 421);
ht.Add(839, 839);
ht.Add(840, 21);
ht.Add(841, 58);
ht.Add(842, 423);
ht.Add(843, 284);
ht.Add(844, 215);
ht.Add(845, 31);
ht.Add(846, 55);
ht.Add(847, 29);
ht.Add(848, 61);
ht.Add(849, 286);
ht.Add(850, 29);
ht.Add(851, 60);
ht.Add(852, 78);
ht.Add(853, 853);
ht.Add(854, 70);
ht.Add(855, 30);
ht.Add(856, 113);
ht.Add(857, 857);
ht.Add(858, 29);
ht.Add(859, 859);
ht.Add(860, 52);
ht.Add(861, 51);
ht.Add(862, 433);
ht.Add(863, 863);
ht.Add(864, 19);
ht.Add(865, 178);
ht.Add(866, 435);
ht.Add(867, 37);
ht.Add(868, 42);
ht.Add(869, 90);
ht.Add(870, 39);
ht.Add(871, 80);
ht.Add(872, 115);
ht.Add(873, 103);
ht.Add(874, 44);
ht.Add(875, 22);
ht.Add(876, 80);
ht.Add(877, 877);
ht.Add(878, 441);
ht.Add(879, 296);
ht.Add(880, 24);
ht.Add(881, 881);
ht.Add(882, 22);
ht.Add(883, 883);
ht.Add(884, 34);
ht.Add(885, 67);
ht.Add(886, 445);
ht.Add(887, 887);
ht.Add(888, 46);
ht.Add(889, 134);
ht.Add(890, 96);
ht.Add(891, 23);
ht.Add(892, 227);
ht.Add(893, 66);
ht.Add(894, 154);
ht.Add(895, 184);
ht.Add(896, 21);
ht.Add(897, 39);
ht.Add(898, 451);
ht.Add(899, 60);
ht.Add(900, 20);
ht.Add(901, 70);
ht.Add(902, 54);
ht.Add(903, 53);
ht.Add(904, 119);
ht.Add(905, 186);
ht.Add(906, 156);
ht.Add(907, 907);
ht.Add(908, 231);
ht.Add(909, 107);
ht.Add(910, 27);
ht.Add(911, 911);
ht.Add(912, 30);
ht.Add(913, 94);
ht.Add(914, 459);
ht.Add(915, 69);
ht.Add(916, 233);
ht.Add(917, 138);
ht.Add(918, 28);
ht.Add(919, 919);
ht.Add(920, 34);
ht.Add(921, 310);
ht.Add(922, 463);
ht.Add(923, 84);
ht.Add(924, 25);
ht.Add(925, 47);
ht.Add(926, 465);
ht.Add(927, 109);
ht.Add(928, 39);
ht.Add(929, 929);
ht.Add(930, 41);
ht.Add(931, 33);
ht.Add(932, 237);
ht.Add(933, 314);
ht.Add(934, 469);
ht.Add(935, 33);
ht.Add(936, 25);
ht.Add(937, 937);
ht.Add(938, 76);
ht.Add(939, 316);
ht.Add(940, 56);
ht.Add(941, 941);
ht.Add(942, 162);
ht.Add(943, 64);
ht.Add(944, 67);
ht.Add(945, 21);
ht.Add(946, 56);
ht.Add(947, 947);
ht.Add(948, 86);
ht.Add(949, 86);
ht.Add(950, 31);
ht.Add(951, 320);
ht.Add(952, 30);
ht.Add(953, 953);
ht.Add(954, 61);
ht.Add(955, 196);
ht.Add(956, 243);
ht.Add(957, 43);
ht.Add(958, 481);
ht.Add(959, 144);
ht.Add(960, 20);
ht.Add(961, 62);
ht.Add(962, 52);
ht.Add(963, 113);
ht.Add(964, 245);
ht.Add(965, 198);
ht.Add(966, 35);
ht.Add(967, 967);
ht.Add(968, 28);
ht.Add(969, 39);
ht.Add(970, 104);
ht.Add(971, 971);
ht.Add(972, 19);
ht.Add(973, 146);
ht.Add(974, 489);
ht.Add(975, 26);
ht.Add(976, 69);
ht.Add(977, 977);
ht.Add(978, 168);
ht.Add(979, 100);
ht.Add(980, 23);
ht.Add(981, 115);
ht.Add(982, 493);
ht.Add(983, 983);
ht.Add(984, 50);
ht.Add(985, 202);
ht.Add(986, 48);
ht.Add(987, 57);
ht.Add(988, 36);
ht.Add(989, 66);
ht.Add(990, 24);
ht.Add(991, 991);
ht.Add(992, 41);
ht.Add(993, 334);
ht.Add(994, 80);
ht.Add(995, 204);
ht.Add(996, 90);
ht.Add(997, 997);
ht.Add(998, 501);
ht.Add(999, 46);
ht.Add(1000, 21);
}
public int MinSteps(int n)
{
return (int)ht[n];
}
}
The problem is this one, take a look: https://leetcode.com/problems/2-keys-keyboard/description/
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:
Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).Paste: You can paste the characters which are copied last time.
Given a number
n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
Example 1:
Input: 3 Output: 3 Explanation: Intitally, we have one character 'A'. In step 1, we use Copy All operation. In step 2, we use Paste operation to get 'AA'. In step 3, we use Paste operation to get 'AAA'.
The solution I came up with was a breadth-first-search (BFS) where the transitions (copy or paste) are the enqueueing steps. So far so good, but unfortunately the code timed out towards the very last steps. Here is the improvisation though: the input asked was from 1..1000. Now that's tiny. What I could do then was using the BFS code (which actually runs relatively fast) pre-compute all answers from 1..1000, create a hashtable with all the answers, and simply index the hashtable. Hence, the first solution, although workable, did not make the cut, whereas the second one did. Both solutions below. Cheers, Marcelo.
Solution 1 (BFS, times out, but works):
public class Solution
{
public int MinSteps(int n)
{
Queue queue = new Queue();
Hashtable alreadySeen = new Hashtable();
EnqueueItem ei = new EnqueueItem("A", "", 0, null);
alreadySeen.Add(ei.current + "@" + ei.paste, true);
queue.Enqueue(ei);
while (queue.Count > 0)
{
EnqueueItem currentItem = (EnqueueItem)queue.Dequeue();
if (currentItem.current.Length == n)
{
//PrintBacktrack(currentItem);
return currentItem.numberSteps;
}
//Copy
if (currentItem.current.Length <= n && currentItem.paste.Length > 0 && !alreadySeen.ContainsKey(currentItem.current + currentItem.paste + "@" + currentItem.paste))
{
EnqueueItem currentItemCopy = new EnqueueItem(currentItem.current + currentItem.paste, currentItem.paste, currentItem.numberSteps + 1, currentItem);
alreadySeen.Add(currentItem.current + currentItem.paste + "@" + currentItem.paste, true);
queue.Enqueue(currentItemCopy);
}
//Paste
if (currentItem.current.Length <= n && !alreadySeen.ContainsKey(currentItem.current + "@" + currentItem.current))
{
EnqueueItem currentItemPaste = new EnqueueItem(currentItem.current, currentItem.current, currentItem.numberSteps + 1, currentItem);
alreadySeen.Add(currentItem.current + "@" + currentItem.current, true);
queue.Enqueue(currentItemPaste);
}
}
return -1;
}
private void PrintBacktrack(EnqueueItem ei)
{
if (ei.from != null) PrintBacktrack(ei.from);
if (ei.from == null) return;
if (ei.current == ei.paste) Console.WriteLine("Step {0}: pasted '{1}' to the clipboard. Current: {2}. Clipboard = {3}", ei.numberSteps, ei.current, ei.current, ei.paste);
else Console.WriteLine("Step {0}: copied '{1}' from the clipboard. Current: {2}. Clipboard = {3}", ei.numberSteps, ei.paste, ei.current, ei.paste);
}
private class EnqueueItem
{
public string current = "";
public string paste = "";
public int numberSteps = 0;
public EnqueueItem from = null;
public EnqueueItem(string current,
string paste,
int numberSteps,
EnqueueItem from)
{
this.current = current;
this.paste = paste;
this.numberSteps = numberSteps;
if (from != null)
{
this.from = new EnqueueItem(from.current, from.paste, from.numberSteps, from.from);
}
}
}
}
public class Solution {
private Hashtable ht = null;
public Solution()
{
ht = new Hashtable();
ht.Add(1, 0);
ht.Add(2, 2);
ht.Add(3, 3);
ht.Add(4, 4);
ht.Add(5, 5);
ht.Add(6, 5);
ht.Add(7, 7);
ht.Add(8, 6);
ht.Add(9, 6);
ht.Add(10, 7);
ht.Add(11, 11);
ht.Add(12, 7);
ht.Add(13, 13);
ht.Add(14, 9);
ht.Add(15, 8);
ht.Add(16, 8);
ht.Add(17, 17);
ht.Add(18, 8);
ht.Add(19, 19);
ht.Add(20, 9);
ht.Add(21, 10);
ht.Add(22, 13);
ht.Add(23, 23);
ht.Add(24, 9);
ht.Add(25, 10);
ht.Add(26, 15);
ht.Add(27, 9);
ht.Add(28, 11);
ht.Add(29, 29);
ht.Add(30, 10);
ht.Add(31, 31);
ht.Add(32, 10);
ht.Add(33, 14);
ht.Add(34, 19);
ht.Add(35, 12);
ht.Add(36, 10);
ht.Add(37, 37);
ht.Add(38, 21);
ht.Add(39, 16);
ht.Add(40, 11);
ht.Add(41, 41);
ht.Add(42, 12);
ht.Add(43, 43);
ht.Add(44, 15);
ht.Add(45, 11);
ht.Add(46, 25);
ht.Add(47, 47);
ht.Add(48, 11);
ht.Add(49, 14);
ht.Add(50, 12);
ht.Add(51, 20);
ht.Add(52, 17);
ht.Add(53, 53);
ht.Add(54, 11);
ht.Add(55, 16);
ht.Add(56, 13);
ht.Add(57, 22);
ht.Add(58, 31);
ht.Add(59, 59);
ht.Add(60, 12);
ht.Add(61, 61);
ht.Add(62, 33);
ht.Add(63, 13);
ht.Add(64, 12);
ht.Add(65, 18);
ht.Add(66, 16);
ht.Add(67, 67);
ht.Add(68, 21);
ht.Add(69, 26);
ht.Add(70, 14);
ht.Add(71, 71);
ht.Add(72, 12);
ht.Add(73, 73);
ht.Add(74, 39);
ht.Add(75, 13);
ht.Add(76, 23);
ht.Add(77, 18);
ht.Add(78, 18);
ht.Add(79, 79);
ht.Add(80, 13);
ht.Add(81, 12);
ht.Add(82, 43);
ht.Add(83, 83);
ht.Add(84, 14);
ht.Add(85, 22);
ht.Add(86, 45);
ht.Add(87, 32);
ht.Add(88, 17);
ht.Add(89, 89);
ht.Add(90, 13);
ht.Add(91, 20);
ht.Add(92, 27);
ht.Add(93, 34);
ht.Add(94, 49);
ht.Add(95, 24);
ht.Add(96, 13);
ht.Add(97, 97);
ht.Add(98, 16);
ht.Add(99, 17);
ht.Add(100, 14);
ht.Add(101, 101);
ht.Add(102, 22);
ht.Add(103, 103);
ht.Add(104, 19);
ht.Add(105, 15);
ht.Add(106, 55);
ht.Add(107, 107);
ht.Add(108, 13);
ht.Add(109, 109);
ht.Add(110, 18);
ht.Add(111, 40);
ht.Add(112, 15);
ht.Add(113, 113);
ht.Add(114, 24);
ht.Add(115, 28);
ht.Add(116, 33);
ht.Add(117, 19);
ht.Add(118, 61);
ht.Add(119, 24);
ht.Add(120, 14);
ht.Add(121, 22);
ht.Add(122, 63);
ht.Add(123, 44);
ht.Add(124, 35);
ht.Add(125, 15);
ht.Add(126, 15);
ht.Add(127, 127);
ht.Add(128, 14);
ht.Add(129, 46);
ht.Add(130, 20);
ht.Add(131, 131);
ht.Add(132, 18);
ht.Add(133, 26);
ht.Add(134, 69);
ht.Add(135, 14);
ht.Add(136, 23);
ht.Add(137, 137);
ht.Add(138, 28);
ht.Add(139, 139);
ht.Add(140, 16);
ht.Add(141, 50);
ht.Add(142, 73);
ht.Add(143, 24);
ht.Add(144, 14);
ht.Add(145, 34);
ht.Add(146, 75);
ht.Add(147, 17);
ht.Add(148, 41);
ht.Add(149, 149);
ht.Add(150, 15);
ht.Add(151, 151);
ht.Add(152, 25);
ht.Add(153, 23);
ht.Add(154, 20);
ht.Add(155, 36);
ht.Add(156, 20);
ht.Add(157, 157);
ht.Add(158, 81);
ht.Add(159, 56);
ht.Add(160, 15);
ht.Add(161, 30);
ht.Add(162, 14);
ht.Add(163, 163);
ht.Add(164, 45);
ht.Add(165, 19);
ht.Add(166, 85);
ht.Add(167, 167);
ht.Add(168, 16);
ht.Add(169, 26);
ht.Add(170, 24);
ht.Add(171, 25);
ht.Add(172, 47);
ht.Add(173, 173);
ht.Add(174, 34);
ht.Add(175, 17);
ht.Add(176, 19);
ht.Add(177, 62);
ht.Add(178, 91);
ht.Add(179, 179);
ht.Add(180, 15);
ht.Add(181, 181);
ht.Add(182, 22);
ht.Add(183, 64);
ht.Add(184, 29);
ht.Add(185, 42);
ht.Add(186, 36);
ht.Add(187, 28);
ht.Add(188, 51);
ht.Add(189, 16);
ht.Add(190, 26);
ht.Add(191, 191);
ht.Add(192, 15);
ht.Add(193, 193);
ht.Add(194, 99);
ht.Add(195, 21);
ht.Add(196, 18);
ht.Add(197, 197);
ht.Add(198, 19);
ht.Add(199, 199);
ht.Add(200, 16);
ht.Add(201, 70);
ht.Add(202, 103);
ht.Add(203, 36);
ht.Add(204, 24);
ht.Add(205, 46);
ht.Add(206, 105);
ht.Add(207, 29);
ht.Add(208, 21);
ht.Add(209, 30);
ht.Add(210, 17);
ht.Add(211, 211);
ht.Add(212, 57);
ht.Add(213, 74);
ht.Add(214, 109);
ht.Add(215, 48);
ht.Add(216, 15);
ht.Add(217, 38);
ht.Add(218, 111);
ht.Add(219, 76);
ht.Add(220, 20);
ht.Add(221, 30);
ht.Add(222, 42);
ht.Add(223, 223);
ht.Add(224, 17);
ht.Add(225, 16);
ht.Add(226, 115);
ht.Add(227, 227);
ht.Add(228, 26);
ht.Add(229, 229);
ht.Add(230, 30);
ht.Add(231, 21);
ht.Add(232, 35);
ht.Add(233, 233);
ht.Add(234, 21);
ht.Add(235, 52);
ht.Add(236, 63);
ht.Add(237, 82);
ht.Add(238, 26);
ht.Add(239, 239);
ht.Add(240, 16);
ht.Add(241, 241);
ht.Add(242, 24);
ht.Add(243, 15);
ht.Add(244, 65);
ht.Add(245, 19);
ht.Add(246, 46);
ht.Add(247, 32);
ht.Add(248, 37);
ht.Add(249, 86);
ht.Add(250, 17);
ht.Add(251, 251);
ht.Add(252, 17);
ht.Add(253, 34);
ht.Add(254, 129);
ht.Add(255, 25);
ht.Add(256, 16);
ht.Add(257, 257);
ht.Add(258, 48);
ht.Add(259, 44);
ht.Add(260, 22);
ht.Add(261, 35);
ht.Add(262, 133);
ht.Add(263, 263);
ht.Add(264, 20);
ht.Add(265, 58);
ht.Add(266, 28);
ht.Add(267, 92);
ht.Add(268, 71);
ht.Add(269, 269);
ht.Add(270, 16);
ht.Add(271, 271);
ht.Add(272, 25);
ht.Add(273, 23);
ht.Add(274, 139);
ht.Add(275, 21);
ht.Add(276, 30);
ht.Add(277, 277);
ht.Add(278, 141);
ht.Add(279, 37);
ht.Add(280, 18);
ht.Add(281, 281);
ht.Add(282, 52);
ht.Add(283, 283);
ht.Add(284, 75);
ht.Add(285, 27);
ht.Add(286, 26);
ht.Add(287, 48);
ht.Add(288, 16);
ht.Add(289, 34);
ht.Add(290, 36);
ht.Add(291, 100);
ht.Add(292, 77);
ht.Add(293, 293);
ht.Add(294, 19);
ht.Add(295, 64);
ht.Add(296, 43);
ht.Add(297, 20);
ht.Add(298, 151);
ht.Add(299, 36);
ht.Add(300, 17);
ht.Add(301, 50);
ht.Add(302, 153);
ht.Add(303, 104);
ht.Add(304, 27);
ht.Add(305, 66);
ht.Add(306, 25);
ht.Add(307, 307);
ht.Add(308, 22);
ht.Add(309, 106);
ht.Add(310, 38);
ht.Add(311, 311);
ht.Add(312, 22);
ht.Add(313, 313);
ht.Add(314, 159);
ht.Add(315, 18);
ht.Add(316, 83);
ht.Add(317, 317);
ht.Add(318, 58);
ht.Add(319, 40);
ht.Add(320, 17);
ht.Add(321, 110);
ht.Add(322, 32);
ht.Add(323, 36);
ht.Add(324, 16);
ht.Add(325, 23);
ht.Add(326, 165);
ht.Add(327, 112);
ht.Add(328, 47);
ht.Add(329, 54);
ht.Add(330, 21);
ht.Add(331, 331);
ht.Add(332, 87);
ht.Add(333, 43);
ht.Add(334, 169);
ht.Add(335, 72);
ht.Add(336, 18);
ht.Add(337, 337);
ht.Add(338, 28);
ht.Add(339, 116);
ht.Add(340, 26);
ht.Add(341, 42);
ht.Add(342, 27);
ht.Add(343, 21);
ht.Add(344, 49);
ht.Add(345, 31);
ht.Add(346, 175);
ht.Add(347, 347);
ht.Add(348, 36);
ht.Add(349, 349);
ht.Add(350, 19);
ht.Add(351, 22);
ht.Add(352, 21);
ht.Add(353, 353);
ht.Add(354, 64);
ht.Add(355, 76);
ht.Add(356, 93);
ht.Add(357, 27);
ht.Add(358, 181);
ht.Add(359, 359);
ht.Add(360, 17);
ht.Add(361, 38);
ht.Add(362, 183);
ht.Add(363, 25);
ht.Add(364, 24);
ht.Add(365, 78);
ht.Add(366, 66);
ht.Add(367, 367);
ht.Add(368, 31);
ht.Add(369, 47);
ht.Add(370, 44);
ht.Add(371, 60);
ht.Add(372, 38);
ht.Add(373, 373);
ht.Add(374, 30);
ht.Add(375, 18);
ht.Add(376, 53);
ht.Add(377, 42);
ht.Add(378, 18);
ht.Add(379, 379);
ht.Add(380, 28);
ht.Add(381, 130);
ht.Add(382, 193);
ht.Add(383, 383);
ht.Add(384, 17);
ht.Add(385, 23);
ht.Add(386, 195);
ht.Add(387, 49);
ht.Add(388, 101);
ht.Add(389, 389);
ht.Add(390, 23);
ht.Add(391, 40);
ht.Add(392, 20);
ht.Add(393, 134);
ht.Add(394, 199);
ht.Add(395, 84);
ht.Add(396, 21);
ht.Add(397, 397);
ht.Add(398, 201);
ht.Add(399, 29);
ht.Add(400, 18);
ht.Add(401, 401);
ht.Add(402, 72);
ht.Add(403, 44);
ht.Add(404, 105);
ht.Add(405, 17);
ht.Add(406, 38);
ht.Add(407, 48);
ht.Add(408, 26);
ht.Add(409, 409);
ht.Add(410, 48);
ht.Add(411, 140);
ht.Add(412, 107);
ht.Add(413, 66);
ht.Add(414, 31);
ht.Add(415, 88);
ht.Add(416, 23);
ht.Add(417, 142);
ht.Add(418, 32);
ht.Add(419, 419);
ht.Add(420, 19);
ht.Add(421, 421);
ht.Add(422, 213);
ht.Add(423, 53);
ht.Add(424, 59);
ht.Add(425, 27);
ht.Add(426, 76);
ht.Add(427, 68);
ht.Add(428, 111);
ht.Add(429, 27);
ht.Add(430, 50);
ht.Add(431, 431);
ht.Add(432, 17);
ht.Add(433, 433);
ht.Add(434, 40);
ht.Add(435, 37);
ht.Add(436, 113);
ht.Add(437, 42);
ht.Add(438, 78);
ht.Add(439, 439);
ht.Add(440, 22);
ht.Add(441, 20);
ht.Add(442, 32);
ht.Add(443, 443);
ht.Add(444, 44);
ht.Add(445, 94);
ht.Add(446, 225);
ht.Add(447, 152);
ht.Add(448, 19);
ht.Add(449, 449);
ht.Add(450, 18);
ht.Add(451, 52);
ht.Add(452, 117);
ht.Add(453, 154);
ht.Add(454, 229);
ht.Add(455, 25);
ht.Add(456, 28);
ht.Add(457, 457);
ht.Add(458, 231);
ht.Add(459, 26);
ht.Add(460, 32);
ht.Add(461, 461);
ht.Add(462, 23);
ht.Add(463, 463);
ht.Add(464, 37);
ht.Add(465, 39);
ht.Add(466, 235);
ht.Add(467, 467);
ht.Add(468, 23);
ht.Add(469, 74);
ht.Add(470, 54);
ht.Add(471, 160);
ht.Add(472, 65);
ht.Add(473, 54);
ht.Add(474, 84);
ht.Add(475, 29);
ht.Add(476, 28);
ht.Add(477, 59);
ht.Add(478, 241);
ht.Add(479, 479);
ht.Add(480, 18);
ht.Add(481, 50);
ht.Add(482, 243);
ht.Add(483, 33);
ht.Add(484, 26);
ht.Add(485, 102);
ht.Add(486, 17);
ht.Add(487, 487);
ht.Add(488, 67);
ht.Add(489, 166);
ht.Add(490, 21);
ht.Add(491, 491);
ht.Add(492, 48);
ht.Add(493, 46);
ht.Add(494, 34);
ht.Add(495, 22);
ht.Add(496, 39);
ht.Add(497, 78);
ht.Add(498, 88);
ht.Add(499, 499);
ht.Add(500, 19);
ht.Add(501, 170);
ht.Add(502, 253);
ht.Add(503, 503);
ht.Add(504, 19);
ht.Add(505, 106);
ht.Add(506, 36);
ht.Add(507, 29);
ht.Add(508, 131);
ht.Add(509, 509);
ht.Add(510, 27);
ht.Add(511, 80);
ht.Add(512, 18);
ht.Add(513, 28);
ht.Add(514, 259);
ht.Add(515, 108);
ht.Add(516, 50);
ht.Add(517, 58);
ht.Add(518, 46);
ht.Add(519, 176);
ht.Add(520, 24);
ht.Add(521, 521);
ht.Add(522, 37);
ht.Add(523, 523);
ht.Add(524, 135);
ht.Add(525, 20);
ht.Add(526, 265);
ht.Add(527, 48);
ht.Add(528, 22);
ht.Add(529, 46);
ht.Add(530, 60);
ht.Add(531, 65);
ht.Add(532, 30);
ht.Add(533, 54);
ht.Add(534, 94);
ht.Add(535, 112);
ht.Add(536, 73);
ht.Add(537, 182);
ht.Add(538, 271);
ht.Add(539, 25);
ht.Add(540, 18);
ht.Add(541, 541);
ht.Add(542, 273);
ht.Add(543, 184);
ht.Add(544, 27);
ht.Add(545, 114);
ht.Add(546, 25);
ht.Add(547, 547);
ht.Add(548, 141);
ht.Add(549, 67);
ht.Add(550, 23);
ht.Add(551, 48);
ht.Add(552, 32);
ht.Add(553, 86);
ht.Add(554, 279);
ht.Add(555, 45);
ht.Add(556, 143);
ht.Add(557, 557);
ht.Add(558, 39);
ht.Add(559, 56);
ht.Add(560, 20);
ht.Add(561, 31);
ht.Add(562, 283);
ht.Add(563, 563);
ht.Add(564, 54);
ht.Add(565, 118);
ht.Add(566, 285);
ht.Add(567, 19);
ht.Add(568, 77);
ht.Add(569, 569);
ht.Add(570, 29);
ht.Add(571, 571);
ht.Add(572, 28);
ht.Add(573, 194);
ht.Add(574, 50);
ht.Add(575, 33);
ht.Add(576, 18);
ht.Add(577, 577);
ht.Add(578, 36);
ht.Add(579, 196);
ht.Add(580, 38);
ht.Add(581, 90);
ht.Add(582, 102);
ht.Add(583, 64);
ht.Add(584, 79);
ht.Add(585, 24);
ht.Add(586, 295);
ht.Add(587, 587);
ht.Add(588, 21);
ht.Add(589, 50);
ht.Add(590, 66);
ht.Add(591, 200);
ht.Add(592, 45);
ht.Add(593, 593);
ht.Add(594, 22);
ht.Add(595, 29);
ht.Add(596, 153);
ht.Add(597, 202);
ht.Add(598, 38);
ht.Add(599, 599);
ht.Add(600, 19);
ht.Add(601, 601);
ht.Add(602, 52);
ht.Add(603, 73);
ht.Add(604, 155);
ht.Add(605, 27);
ht.Add(606, 106);
ht.Add(607, 607);
ht.Add(608, 29);
ht.Add(609, 39);
ht.Add(610, 68);
ht.Add(611, 60);
ht.Add(612, 27);
ht.Add(613, 613);
ht.Add(614, 309);
ht.Add(615, 49);
ht.Add(616, 24);
ht.Add(617, 617);
ht.Add(618, 108);
ht.Add(619, 619);
ht.Add(620, 40);
ht.Add(621, 32);
ht.Add(622, 313);
ht.Add(623, 96);
ht.Add(624, 24);
ht.Add(625, 20);
ht.Add(626, 315);
ht.Add(627, 33);
ht.Add(628, 161);
ht.Add(629, 54);
ht.Add(630, 20);
ht.Add(631, 631);
ht.Add(632, 85);
ht.Add(633, 214);
ht.Add(634, 319);
ht.Add(635, 132);
ht.Add(636, 60);
ht.Add(637, 27);
ht.Add(638, 42);
ht.Add(639, 77);
ht.Add(640, 19);
ht.Add(641, 641);
ht.Add(642, 112);
ht.Add(643, 643);
ht.Add(644, 34);
ht.Add(645, 51);
ht.Add(646, 38);
ht.Add(647, 647);
ht.Add(648, 18);
ht.Add(649, 70);
ht.Add(650, 25);
ht.Add(651, 41);
ht.Add(652, 167);
ht.Add(653, 653);
ht.Add(654, 114);
ht.Add(655, 136);
ht.Add(656, 49);
ht.Add(657, 79);
ht.Add(658, 56);
ht.Add(659, 659);
ht.Add(660, 23);
ht.Add(661, 661);
ht.Add(662, 333);
ht.Add(663, 33);
ht.Add(664, 89);
ht.Add(665, 31);
ht.Add(666, 45);
ht.Add(667, 52);
ht.Add(668, 171);
ht.Add(669, 226);
ht.Add(670, 74);
ht.Add(671, 72);
ht.Add(672, 20);
ht.Add(673, 673);
ht.Add(674, 339);
ht.Add(675, 19);
ht.Add(676, 30);
ht.Add(677, 677);
ht.Add(678, 118);
ht.Add(679, 104);
ht.Add(680, 28);
ht.Add(681, 230);
ht.Add(682, 44);
ht.Add(683, 683);
ht.Add(684, 29);
ht.Add(685, 142);
ht.Add(686, 23);
ht.Add(687, 232);
ht.Add(688, 51);
ht.Add(689, 66);
ht.Add(690, 33);
ht.Add(691, 691);
ht.Add(692, 177);
ht.Add(693, 24);
ht.Add(694, 349);
ht.Add(695, 144);
ht.Add(696, 38);
ht.Add(697, 58);
ht.Add(698, 351);
ht.Add(699, 236);
ht.Add(700, 21);
ht.Add(701, 701);
ht.Add(702, 24);
ht.Add(703, 56);
ht.Add(704, 23);
ht.Add(705, 55);
ht.Add(706, 355);
ht.Add(707, 108);
ht.Add(708, 66);
ht.Add(709, 709);
ht.Add(710, 78);
ht.Add(711, 85);
ht.Add(712, 95);
ht.Add(713, 54);
ht.Add(714, 29);
ht.Add(715, 29);
ht.Add(716, 183);
ht.Add(717, 242);
ht.Add(718, 361);
ht.Add(719, 719);
ht.Add(720, 19);
ht.Add(721, 110);
ht.Add(722, 40);
ht.Add(723, 244);
ht.Add(724, 185);
ht.Add(725, 39);
ht.Add(726, 27);
ht.Add(727, 727);
ht.Add(728, 26);
ht.Add(729, 18);
ht.Add(730, 80);
ht.Add(731, 60);
ht.Add(732, 68);
ht.Add(733, 733);
ht.Add(734, 369);
ht.Add(735, 22);
ht.Add(736, 33);
ht.Add(737, 78);
ht.Add(738, 49);
ht.Add(739, 739);
ht.Add(740, 46);
ht.Add(741, 35);
ht.Add(742, 62);
ht.Add(743, 743);
ht.Add(744, 40);
ht.Add(745, 154);
ht.Add(746, 375);
ht.Add(747, 89);
ht.Add(748, 32);
ht.Add(749, 114);
ht.Add(750, 20);
ht.Add(751, 751);
ht.Add(752, 55);
ht.Add(753, 254);
ht.Add(754, 44);
ht.Add(755, 156);
ht.Add(756, 20);
ht.Add(757, 757);
ht.Add(758, 381);
ht.Add(759, 37);
ht.Add(760, 30);
ht.Add(761, 761);
ht.Add(762, 132);
ht.Add(763, 116);
ht.Add(764, 195);
ht.Add(765, 28);
ht.Add(766, 385);
ht.Add(767, 72);
ht.Add(768, 19);
ht.Add(769, 769);
ht.Add(770, 25);
ht.Add(771, 260);
ht.Add(772, 197);
ht.Add(773, 773);
ht.Add(774, 51);
ht.Add(775, 41);
ht.Add(776, 103);
ht.Add(777, 47);
ht.Add(778, 391);
ht.Add(779, 60);
ht.Add(780, 25);
ht.Add(781, 82);
ht.Add(782, 42);
ht.Add(783, 38);
ht.Add(784, 22);
ht.Add(785, 162);
ht.Add(786, 136);
ht.Add(787, 787);
ht.Add(788, 201);
ht.Add(789, 266);
ht.Add(790, 86);
ht.Add(791, 120);
ht.Add(792, 23);
ht.Add(793, 74);
ht.Add(794, 399);
ht.Add(795, 61);
ht.Add(796, 203);
ht.Add(797, 797);
ht.Add(798, 31);
ht.Add(799, 64);
ht.Add(800, 20);
ht.Add(801, 95);
ht.Add(802, 403);
ht.Add(803, 84);
ht.Add(804, 74);
ht.Add(805, 35);
ht.Add(806, 46);
ht.Add(807, 272);
ht.Add(808, 107);
ht.Add(809, 809);
ht.Add(810, 19);
ht.Add(811, 811);
ht.Add(812, 40);
ht.Add(813, 274);
ht.Add(814, 50);
ht.Add(815, 168);
ht.Add(816, 28);
ht.Add(817, 62);
ht.Add(818, 411);
ht.Add(819, 26);
ht.Add(820, 50);
ht.Add(821, 821);
ht.Add(822, 142);
ht.Add(823, 823);
ht.Add(824, 109);
ht.Add(825, 24);
ht.Add(826, 68);
ht.Add(827, 827);
ht.Add(828, 33);
ht.Add(829, 829);
ht.Add(830, 90);
ht.Add(831, 280);
ht.Add(832, 25);
ht.Add(833, 31);
ht.Add(834, 144);
ht.Add(835, 172);
ht.Add(836, 34);
ht.Add(837, 40);
ht.Add(838, 421);
ht.Add(839, 839);
ht.Add(840, 21);
ht.Add(841, 58);
ht.Add(842, 423);
ht.Add(843, 284);
ht.Add(844, 215);
ht.Add(845, 31);
ht.Add(846, 55);
ht.Add(847, 29);
ht.Add(848, 61);
ht.Add(849, 286);
ht.Add(850, 29);
ht.Add(851, 60);
ht.Add(852, 78);
ht.Add(853, 853);
ht.Add(854, 70);
ht.Add(855, 30);
ht.Add(856, 113);
ht.Add(857, 857);
ht.Add(858, 29);
ht.Add(859, 859);
ht.Add(860, 52);
ht.Add(861, 51);
ht.Add(862, 433);
ht.Add(863, 863);
ht.Add(864, 19);
ht.Add(865, 178);
ht.Add(866, 435);
ht.Add(867, 37);
ht.Add(868, 42);
ht.Add(869, 90);
ht.Add(870, 39);
ht.Add(871, 80);
ht.Add(872, 115);
ht.Add(873, 103);
ht.Add(874, 44);
ht.Add(875, 22);
ht.Add(876, 80);
ht.Add(877, 877);
ht.Add(878, 441);
ht.Add(879, 296);
ht.Add(880, 24);
ht.Add(881, 881);
ht.Add(882, 22);
ht.Add(883, 883);
ht.Add(884, 34);
ht.Add(885, 67);
ht.Add(886, 445);
ht.Add(887, 887);
ht.Add(888, 46);
ht.Add(889, 134);
ht.Add(890, 96);
ht.Add(891, 23);
ht.Add(892, 227);
ht.Add(893, 66);
ht.Add(894, 154);
ht.Add(895, 184);
ht.Add(896, 21);
ht.Add(897, 39);
ht.Add(898, 451);
ht.Add(899, 60);
ht.Add(900, 20);
ht.Add(901, 70);
ht.Add(902, 54);
ht.Add(903, 53);
ht.Add(904, 119);
ht.Add(905, 186);
ht.Add(906, 156);
ht.Add(907, 907);
ht.Add(908, 231);
ht.Add(909, 107);
ht.Add(910, 27);
ht.Add(911, 911);
ht.Add(912, 30);
ht.Add(913, 94);
ht.Add(914, 459);
ht.Add(915, 69);
ht.Add(916, 233);
ht.Add(917, 138);
ht.Add(918, 28);
ht.Add(919, 919);
ht.Add(920, 34);
ht.Add(921, 310);
ht.Add(922, 463);
ht.Add(923, 84);
ht.Add(924, 25);
ht.Add(925, 47);
ht.Add(926, 465);
ht.Add(927, 109);
ht.Add(928, 39);
ht.Add(929, 929);
ht.Add(930, 41);
ht.Add(931, 33);
ht.Add(932, 237);
ht.Add(933, 314);
ht.Add(934, 469);
ht.Add(935, 33);
ht.Add(936, 25);
ht.Add(937, 937);
ht.Add(938, 76);
ht.Add(939, 316);
ht.Add(940, 56);
ht.Add(941, 941);
ht.Add(942, 162);
ht.Add(943, 64);
ht.Add(944, 67);
ht.Add(945, 21);
ht.Add(946, 56);
ht.Add(947, 947);
ht.Add(948, 86);
ht.Add(949, 86);
ht.Add(950, 31);
ht.Add(951, 320);
ht.Add(952, 30);
ht.Add(953, 953);
ht.Add(954, 61);
ht.Add(955, 196);
ht.Add(956, 243);
ht.Add(957, 43);
ht.Add(958, 481);
ht.Add(959, 144);
ht.Add(960, 20);
ht.Add(961, 62);
ht.Add(962, 52);
ht.Add(963, 113);
ht.Add(964, 245);
ht.Add(965, 198);
ht.Add(966, 35);
ht.Add(967, 967);
ht.Add(968, 28);
ht.Add(969, 39);
ht.Add(970, 104);
ht.Add(971, 971);
ht.Add(972, 19);
ht.Add(973, 146);
ht.Add(974, 489);
ht.Add(975, 26);
ht.Add(976, 69);
ht.Add(977, 977);
ht.Add(978, 168);
ht.Add(979, 100);
ht.Add(980, 23);
ht.Add(981, 115);
ht.Add(982, 493);
ht.Add(983, 983);
ht.Add(984, 50);
ht.Add(985, 202);
ht.Add(986, 48);
ht.Add(987, 57);
ht.Add(988, 36);
ht.Add(989, 66);
ht.Add(990, 24);
ht.Add(991, 991);
ht.Add(992, 41);
ht.Add(993, 334);
ht.Add(994, 80);
ht.Add(995, 204);
ht.Add(996, 90);
ht.Add(997, 997);
ht.Add(998, 501);
ht.Add(999, 46);
ht.Add(1000, 21);
}
public int MinSteps(int n)
{
return (int)ht[n];
}
}
Marcelo, when I read "cheating" word in your first sentence I thought that you'd be using some clever mathematical observation based on the properties of the generated sequence :) Anyways, the solution I came up with is based on a simple observation - in order to find the number of operations to get number n you can try to find the largest chunk you already know how to create, copy and paste it required number of times. For even numbers the cost can be calculated using this simple formula T(n) = T(n/2) + cost_of_copy + cost_of_paste. For non-prime numbers, we need to find the largest factor (to minimize the number of pastes), which we can copy and paste and for prime numbers we obviously have to copy a single digit, which is most expensive. This the formula above suggests overlapping problems, dynamic programming approach seems most appropriate. I suspect that top-down approach with memoization may be somewhat more efficient, but I decided to use a bottom-up. My naive implementation with some explanation attempt can be found below:
ReplyDeleteclass Solution {
public:
int minSteps(int n) {
int d[n+1];
d[1] = 0;
const int copy_cost = 1;
const int paste_cost = 1;
for (int i = 2; i <= n; ++i) {
// find the largest chunk we can copy and paste to get the desired length
// the smaller the factor, the larger the chunk, but factor 1 obviously
// won't work because it would mean that we already have the cost of n
for (int factor = 2; factor <= i; ++factor) {
if (i % factor == 0) {
d[i] = d[i/factor] + copy_cost + paste_cost * (factor - 1);
break;
}
}
}
return d[n];
}
};
Have a splendid rest of the weekend!
Taras
:) Clever!!! Taras, take a look at my latest post, and see if you can figure out what's going on with the investment plan. I couldn't....
ReplyDeleteAfter relying on computers for so long to do everything for me, my brain can no longer process math or statistics, but it seems like the problem in your post can be modeled using a Markov Chain. You should be able to build a transition matrix and compute the probability of ending up in a ruined state. This basically seems like a variation of a Gambler's Ruin problem (http://www.columbia.edu/~ks20/FE-Notes/4700-07-Notes-GR.pdf). I don't want to spoil all the fun of working through this problem for you :)
Delete