Stack and Its Complexity

𝑫𝒆𝒇𝒊𝒏𝒊𝒕𝒊𝒐𝒏: - 𝑨 𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝒂𝒏 𝒐𝒓𝒅𝒆𝒓𝒆𝒅 𝒍𝒊𝒔𝒕 (𝒊. 𝒆. ,𝒍𝒊𝒔𝒕𝒆𝒅 𝒊𝒏 𝒂 𝒔𝒑𝒆𝒄𝒊𝒇𝒊𝒄 𝒐𝒓𝒅𝒆𝒓 (𝒐𝒓𝒅𝒆𝒓𝒆𝒅))𝒊𝒏 𝒘𝒉𝒊𝒄𝒉 𝒊𝒏𝒔𝒆𝒓𝒕𝒊𝒐𝒏 𝒂𝒏𝒅 𝒅𝒆𝒍𝒆𝒕𝒊𝒐𝒏 𝒂𝒓𝒆 𝒅𝒐𝒏𝒆 𝒂𝒕 𝒐𝒏𝒆 𝒆𝒏𝒅, 𝒄𝒂𝒍𝒍𝒆𝒅 𝒕𝒐𝒑.

𝑨. 𝑹𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌 𝒃𝒂𝒔𝒆𝒅 𝒐𝒏 𝑹𝒆𝒂𝒍 𝑷𝒉𝒚𝒔𝒊𝒄𝒂𝒍 𝑬𝒏𝒕𝒊𝒕𝒚

𝑶𝒏 𝒓𝒆𝒂𝒍 𝒑𝒉𝒚𝒔𝒊𝒄𝒂𝒍 𝒆𝒏𝒕𝒊𝒕𝒚 𝒘𝒆 𝒄𝒂𝒏 𝒕𝒂𝒌𝒆 𝒆𝒙𝒂𝒎𝒑𝒍𝒆 𝒐𝒇 :



𝑰𝒇 𝒘𝒆 𝒕𝒂𝒌𝒆 𝒕𝒉𝒆 𝒆𝒙𝒂𝒎𝒑𝒍𝒆 𝒐𝒇 𝑫𝒊𝒔𝒉, 𝒘𝒉𝒊𝒍𝒆 𝒂𝒓𝒓𝒂𝒏𝒈𝒊𝒏𝒈 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒐𝒇 𝒅𝒊𝒔𝒉𝒆𝒔, 𝒘𝒆 𝒌𝒆𝒆𝒑 𝒐𝒏𝒆 𝒅𝒊𝒔𝒉 𝒖𝒑𝒐𝒏 𝒂𝒏𝒐𝒕𝒉𝒆𝒓 𝒊.𝒆., 𝒕𝒉𝒆 𝒎𝒆𝒄𝒉𝒂𝒏𝒊𝒔𝒎 𝒄𝒂𝒍𝒍𝒆𝒅 “𝑳𝒂𝒔𝒕 𝑰𝒏” 𝒂𝒏𝒅 𝒏𝒐𝒘 𝒊𝒇 𝒘𝒆 𝒘𝒂𝒏𝒕 𝒕𝒐 𝒓𝒆𝒎𝒐𝒗𝒆 𝒂 𝒅𝒊𝒔𝒉 𝒘𝒆 𝒔𝒉𝒐𝒖𝒍𝒅 𝒓𝒆𝒎𝒐𝒗𝒆 𝒕𝒉𝒆 𝒇𝒊𝒓𝒔𝒕 𝒅𝒊𝒔𝒉, 𝒕𝒉𝒊𝒔 𝒎𝒆𝒄𝒉𝒂𝒏𝒊𝒔𝒎 𝒊𝒔 𝒄𝒂𝒍𝒍𝒆𝒅 “𝑭𝒊𝒓𝒔𝒕 𝑶𝒖𝒕”, 𝒉𝒆𝒏𝒄𝒆 𝒘𝒉𝒐𝒍𝒆 𝒎𝒆𝒄𝒉𝒂𝒏𝒊𝒔𝒎 𝒊𝒔 𝒄𝒂𝒍𝒍𝒆𝒅: “𝑳𝒂𝒔𝒕 𝒊𝒏 𝑭𝒊𝒓𝒔𝒕 𝑶𝒖𝒕”. 𝑶𝒓 𝒊𝒇 𝒘𝒆 𝒔𝒂𝒚 𝒍𝒂𝒔𝒕 𝒅𝒊𝒔𝒉 𝒊𝒔 𝑭𝒊𝒓𝒔𝒕 𝑫𝒊𝒔𝒉 𝒂𝒏𝒅 𝑭𝒊𝒓𝒔𝒕 𝑫𝒊𝒔𝒉 𝒂𝒔 𝑳𝒂𝒔𝒕 𝑫𝒊𝒔𝒉, 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒃𝒆𝒄𝒐𝒎𝒆 “𝑭𝒊𝒓𝒔𝒕 𝑰𝒏 𝑳𝒂𝒔𝒕 𝑶𝒖𝒕” 𝒎𝒆𝒄𝒉𝒂𝒏𝒊𝒔𝒎.

𝑩. 𝑴𝒆𝒎𝒐𝒓𝒚 𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒏 𝑹𝒂𝒏𝒅𝒐𝒎 𝑨𝒄𝒄𝒆𝒔𝒔 𝑴𝒆𝒎𝒐𝒓𝒚(𝑹𝑨𝑴)

1. 𝑷𝒓𝒐𝒈𝒓𝒂𝒎 𝑪𝒐𝒖𝒏𝒕𝒆𝒓 : - 𝑰𝒕 𝒊𝒔 𝒂 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒕𝒉𝒂𝒕 𝒎𝒂𝒏𝒂𝒈𝒆𝒔 𝒕𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔 𝒕𝒉𝒂𝒕 𝒕𝒐 𝒃𝒆 𝒆𝒙𝒆𝒄𝒖𝒕𝒆𝒅 𝒏𝒆𝒙𝒕. 𝑻𝒉𝒂𝒕 𝒊𝒔 𝒔𝒊𝒎𝒑𝒍𝒚 𝒂 𝒎𝒂𝒏𝒂𝒈𝒆𝒓 𝒘𝒉𝒊𝒄𝒉 𝒕𝒆𝒍𝒍𝒔 𝑪𝑷𝑼 𝒕𝒉𝒂𝒕 𝒘𝒉𝒂𝒕 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝒕𝒐 𝒃𝒆 𝒆𝒙𝒆𝒄𝒖𝒕𝒆𝒅.

1.𝒂. 𝑷𝒓𝒐𝒈𝒓𝒂𝒎 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔: 𝑻𝒉𝒆 𝒄𝒐𝒅𝒆𝒔 𝒕𝒉𝒂𝒕 𝒂𝒓𝒆 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒓𝒆 𝒔𝒕𝒐𝒓𝒆𝒅 𝒂𝒔 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔 𝒊𝒏 𝑨𝒔𝒔𝒆𝒎𝒃𝒍𝒚 𝑳𝒂𝒏𝒈𝒖𝒂𝒈𝒆. 𝑨𝒔𝒔𝒆𝒎𝒃𝒍𝒚 𝑳𝒂𝒏𝒈𝒖𝒂𝒈𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔 𝒂𝒓𝒆 𝒄𝒂𝒍𝒍𝒆𝒅 ‘𝒎𝒂𝒄𝒉𝒊𝒏𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔.

𝑺𝒖𝒄𝒉 𝒂𝒔: 𝑵 = 𝑰+𝑱+𝑲,𝒘𝒉𝒆𝒓𝒆 𝑰 𝒊𝒔 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 201,𝑱 𝒊𝒏 202 ,𝑲 𝒊𝒏 203 𝒂𝒏𝒅 𝑵 𝒊𝒏 204.

𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔:

1. 𝑳𝒐𝒂𝒅 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 201 𝒊𝒏 𝑨𝒄𝒄𝒖𝒎𝒖𝒍𝒂𝒕𝒐𝒓.

2.𝑨𝒅𝒅 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕𝒔 𝒐𝒇 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 202 𝒕𝒐 𝒕𝒉𝒆 𝑨𝒄𝒄𝒖𝒎𝒖𝒍𝒂𝒕𝒐𝒓.

3.𝑨𝒅𝒅 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕𝒔 𝒐𝒇 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 203 𝒕𝒐 𝒕𝒉𝒆 𝑨𝒄𝒄𝒖𝒎𝒖𝒍𝒂𝒕𝒐𝒓.

4.𝑺𝒕𝒐𝒓𝒆 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝑨𝒄𝒄𝒖𝒎𝒖𝒍𝒂𝒕𝒐𝒓 𝒊𝒏 𝒕𝒉𝒆 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 204.

𝑰𝒏 𝑨𝒔𝒔𝒆𝒎𝒃𝒍𝒚 𝑳𝒂𝒏𝒈𝒖𝒂𝒈𝒆 𝒊𝒕 𝒍𝒐𝒐𝒌𝒔 𝒍𝒊𝒌𝒆:

𝑳𝑫𝑨 𝑰

𝑨𝑫𝑫 𝑱

𝑨𝑫𝑫 𝑲

𝑺𝑻𝑨 𝑵

𝑾𝒉𝒆𝒓𝒆 ,𝑳𝑫𝑨→𝑳𝒐𝒂𝒅 𝑨𝒄𝒄𝒖𝒎𝒖𝒍𝒂𝒕𝒐𝒓 𝒂𝒏𝒅 𝑺𝑻𝑨→𝑺𝒕𝒐𝒓𝒆 𝑨𝒄𝒄𝒖𝒎𝒖𝒍𝒂𝒕𝒐𝒓.

𝑨𝒏𝒅 𝒕𝒉𝒆𝒓𝒆 𝒊𝒔 𝒂𝒏 𝒂𝒔𝒔𝒆𝒎𝒃𝒍𝒆𝒓 𝒕𝒉𝒂𝒕 𝒄𝒐𝒏𝒗𝒆𝒓𝒕𝒔 𝒕𝒉𝒆 𝒉𝒊𝒈𝒉-𝒍𝒆𝒗𝒆𝒍 𝒍𝒂𝒏𝒈𝒖𝒂𝒈𝒆 𝒕𝒐 𝒕𝒉𝒆 𝒍𝒐𝒘-𝒍𝒆𝒗𝒆𝒍 𝒂𝒔𝒔𝒆𝒎𝒃𝒍𝒚 𝒍𝒂𝒏𝒈𝒖𝒂𝒈𝒆. 𝑳𝒂𝒕𝒆𝒓 𝒔𝒖𝒄𝒉 𝒍𝒐𝒘 𝒍𝒆𝒗𝒆𝒍 𝒍𝒂𝒏𝒈𝒖𝒂𝒈𝒆 𝒂𝒓𝒆 𝒄𝒐𝒏𝒗𝒆𝒓𝒕𝒆𝒅 𝒕𝒐 𝒃𝒊𝒏𝒂𝒓𝒚 𝒍𝒂𝒏𝒈𝒖𝒂𝒈𝒆 𝒘𝒉𝒊𝒄𝒉 𝒊𝒔 𝒃𝒆𝒕𝒕𝒆𝒓 𝒌𝒏𝒐𝒘𝒏 𝒂𝒔 “𝑴𝒂𝒄𝒉𝒊𝒏𝒆 𝑳𝒆𝒗𝒆𝒍 𝑳𝒂𝒏𝒈𝒖𝒂𝒈𝒆”, 𝒘𝒉𝒆𝒏 𝒔𝒖𝒄𝒉 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔 𝒂𝒓𝒆 𝒆𝒙𝒆𝒄𝒖𝒕𝒆𝒅 𝒃𝒚 𝒕𝒉𝒆 𝒑𝒓𝒐𝒄𝒆𝒔𝒔𝒐𝒓.

• 𝑨𝒄𝒄𝒖𝒎𝒖𝒍𝒂𝒕𝒐𝒓: 𝑨𝒏 𝒂𝒄𝒄𝒖𝒎𝒖𝒍𝒂𝒕𝒐𝒓 𝒊𝒔 𝒂 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒘𝒉𝒊𝒄𝒉 𝒂𝒄𝒕𝒔 𝒂𝒔 𝒊𝒏𝒕𝒆𝒓𝒎𝒆𝒅𝒊𝒂𝒕𝒆 𝒔𝒕𝒐𝒓𝒂𝒈𝒆 𝒐𝒇 𝒂𝒓𝒊𝒕𝒉𝒎𝒆𝒕𝒊𝒄 𝒂𝒏𝒅 𝒍𝒐𝒈𝒊𝒄 𝒅𝒂𝒕𝒂 𝒊𝒏 𝒂 𝒄𝒐𝒎𝒑𝒖𝒕𝒆𝒓'𝒔 𝒄𝒆𝒏𝒕𝒓𝒂𝒍 𝒑𝒓𝒐𝒄𝒆𝒔𝒔𝒊𝒏𝒈 𝒖𝒏𝒊𝒕 (𝑪𝑷𝑼).

2. 𝑨𝒅𝒅𝒓𝒆𝒔𝒔 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓, 𝒃𝒆𝒕𝒕𝒆𝒓 𝒌𝒏𝒐𝒘𝒏 𝒂𝒔 𝑴𝒆𝒎𝒐𝒓𝒚 𝑨𝒅𝒅𝒓𝒆𝒔𝒔 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓: :



1. 𝑻𝒉𝒆 𝒊𝒏𝒇𝒐𝒓𝒎𝒂𝒕𝒊𝒐𝒏 𝒕𝒓𝒂𝒏𝒔𝒇𝒆𝒓 𝒕𝒐 𝒂𝒏𝒅 𝒇𝒓𝒐𝒎 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓𝒔 𝒊𝒏 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒏𝒅 𝒕𝒉𝒆 𝒆𝒙𝒕𝒆𝒓𝒏𝒂𝒍 𝒆𝒏𝒗𝒊𝒓𝒐𝒏𝒎𝒆𝒏𝒕 𝒊𝒔 𝒄𝒐𝒎𝒎𝒖𝒏𝒊𝒄𝒂𝒕𝒆𝒅 𝒕𝒉𝒓𝒐𝒖𝒈𝒉 𝒐𝒏𝒆 𝒄𝒐𝒎𝒎𝒐𝒏 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒄𝒂𝒍𝒍𝒆𝒅 𝒕𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒃𝒖𝒇𝒇𝒆𝒓 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 (𝒐𝒕𝒉𝒆𝒓 𝒏𝒂𝒎𝒆𝒔 𝒂𝒓𝒆 𝒅𝒂𝒕𝒂 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓, 𝒊𝒏𝒇𝒐𝒓𝒎𝒂𝒕𝒊𝒐𝒏 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒂𝒏𝒅 𝒔𝒕𝒐𝒓𝒂𝒈𝒆 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓).

2.𝑾𝒉𝒆𝒏 𝒕𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒖𝒏𝒊𝒕 𝒓𝒆𝒄𝒆𝒊𝒗𝒆𝒔 𝒂 𝒘𝒓𝒊𝒕𝒆 𝒄𝒐𝒏𝒕𝒓𝒐𝒍 𝒔𝒊𝒈𝒏𝒂𝒍, 𝒕𝒉𝒆, 𝒊𝒏𝒕𝒆𝒓𝒏𝒂𝒍 𝒄𝒐𝒏𝒕𝒓𝒐𝒍 𝒊𝒏𝒕𝒆𝒓𝒑𝒓𝒆𝒕𝒔 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒃𝒖𝒇𝒇𝒆𝒓 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒕𝒐 𝒃𝒆 𝒕𝒉𝒆 𝒃𝒊𝒕 𝒄𝒐𝒏𝒇𝒊𝒈𝒖𝒓𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝒕𝒉𝒆 𝒘𝒐𝒓𝒅 𝒕𝒐 𝒃𝒆 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝒂 𝒎𝒆𝒎𝒐𝒓𝒚 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓.

3.𝑾𝒊𝒕𝒉 𝒂 𝒓𝒆𝒂𝒅 𝒄𝒐𝒏𝒕𝒓𝒐𝒍 𝒔𝒊𝒈𝒏𝒂𝒍, 𝒕𝒉𝒆 𝒊𝒏𝒕𝒆𝒓𝒏𝒂𝒍 𝒄𝒐𝒏𝒕𝒓𝒐𝒍 𝒔𝒆𝒏𝒅𝒔 𝒕𝒉𝒆 𝒘𝒐𝒓𝒅 𝒇𝒓𝒐𝒎 𝒂 𝒎𝒆𝒎𝒐𝒓𝒚 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒊𝒏𝒕𝒐 𝒕𝒉𝒆 𝒃𝒖𝒇𝒇𝒆𝒓 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓.

4.𝑰𝒏 𝒆𝒂𝒄𝒉 𝒄𝒂𝒔𝒆 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒔𝒑𝒆𝒄𝒊𝒇𝒚 𝒕𝒉𝒆 𝒑𝒂𝒓𝒕𝒊𝒄𝒖𝒍𝒂𝒓 𝒎𝒆𝒎𝒐𝒓𝒚 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒓𝒆𝒇𝒆𝒓𝒆𝒏𝒄𝒆𝒅 𝒇𝒐𝒓 𝒘𝒓𝒊𝒕𝒊𝒏𝒈 𝒐𝒓 𝒓𝒆𝒂𝒅𝒊𝒏𝒈.



•𝑴𝑨𝑹 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒔 𝒅𝒊𝒓𝒆𝒄𝒕𝒍𝒚 𝒕𝒐 𝒕𝒉𝒆 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒃𝒖𝒔.

•𝑴𝑩𝑹 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒔 𝒅𝒊𝒓𝒆𝒄𝒕𝒍𝒚 𝒕𝒐 𝒕𝒉𝒆 𝒅𝒂𝒕𝒂 𝒃𝒖𝒔.

•𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓𝒔 𝒆𝒙𝒄𝒉𝒂𝒏𝒈𝒆 𝒅𝒂𝒕𝒂 𝒘𝒊𝒕𝒉 𝑴𝑩𝑹.



𝑪𝒐𝒏𝒔𝒊𝒅𝒆𝒓 𝒂 𝒎𝒆𝒎𝒐𝒓𝒚 𝒖𝒏𝒊𝒕 𝒐𝒇 1024 𝒘𝒐𝒓𝒅𝒔 𝒘𝒊𝒕𝒉 8 𝒃𝒊𝒕𝒔 𝒑𝒆𝒓 𝒘𝒐𝒓𝒅. 𝑻𝒐 𝒔𝒑𝒆𝒄𝒊𝒇𝒚 1024 𝒘𝒐𝒓𝒅𝒔, 𝒘𝒆 𝒏𝒆𝒆𝒅 𝒂𝒏 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒐𝒇 10 𝒃𝒊𝒕𝒔, 𝒔𝒊𝒏𝒄𝒆 2^10=1024. 𝑯𝒆𝒏𝒄𝒆 𝒕𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒉𝒂𝒔 1024 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓𝒔 𝒘𝒊𝒕𝒉 𝒂𝒔𝒔𝒊𝒈𝒏𝒆𝒅 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒏𝒖𝒎𝒃𝒆𝒓𝒔 𝒇𝒓𝒐𝒎 0 𝒕𝒐 1023.

𝑹𝒆𝒂𝒅 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏

𝑹𝒆𝒂𝒅 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒊𝒆𝒔 𝑪𝒐𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒆𝒅 𝒃𝒚 𝑺𝒆𝒎𝒊𝒄𝒐𝒏𝒅𝒖𝒄𝒕𝒐𝒓 𝑰𝑪𝒔

1. 𝑻𝒓𝒂𝒏𝒔𝒇𝒆𝒓 𝒕𝒉𝒆 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒃𝒊𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒆𝒍𝒆𝒄𝒕𝒆𝒅 𝒘𝒐𝒓𝒅 𝒊𝒏𝒕𝒐 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒍𝒊𝒏𝒆𝒔 𝒐𝒇 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒃𝒖𝒔 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝑴𝑨𝑹.

2. 𝑨𝒄𝒕𝒊𝒗𝒂𝒕𝒆 𝒕𝒉𝒆 𝒓𝒆𝒂𝒅 𝒄𝒐𝒏𝒕𝒓𝒐𝒍 𝒊𝒏𝒑𝒖𝒕.



𝑹𝒆𝒂𝒅 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒊𝒆𝒔 𝑪𝒐𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒆𝒅 𝒃𝒚 𝑴𝒂𝒈𝒏𝒆𝒕𝒊𝒄 𝑪𝒐𝒓𝒆



𝑨 𝒅𝒆𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒗𝒆 𝒓𝒆𝒂𝒅 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒕𝒓𝒂𝒏𝒔𝒇𝒆𝒓𝒔 𝒕𝒉𝒆 𝒔𝒆𝒍𝒆𝒄𝒕𝒆𝒅 𝒘𝒐𝒓𝒅 𝒊𝒏𝒕𝒐 𝑴𝑩𝑹 𝒃𝒖𝒕 𝒍𝒆𝒂𝒗𝒆𝒔 𝒕𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒘𝒊𝒕𝒉 𝒂𝒍𝒍 0’𝒔. 𝑵𝒐𝒓𝒎𝒂𝒍 𝒎𝒆𝒎𝒐𝒓𝒚 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒓𝒆𝒒𝒖𝒊𝒓𝒆𝒔 𝒕𝒉𝒂𝒕 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒆𝒍𝒆𝒄𝒕𝒆𝒅 𝒘𝒐𝒓𝒅 𝒓𝒆𝒎𝒂𝒊𝒏 𝒊𝒏 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒇𝒕𝒆𝒓 𝒂 𝒓𝒆𝒂𝒅 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏. 𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆, 𝒊𝒕 𝒊𝒔 𝒏𝒆𝒄𝒆𝒔𝒔𝒂𝒓𝒚 𝒕𝒐 𝒈𝒐 𝒕𝒉𝒓𝒐𝒖𝒈𝒉 𝒂 𝒓𝒆𝒔𝒕𝒐𝒓𝒆 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒕𝒉𝒂𝒕 𝒘𝒓𝒊𝒕𝒆𝒔 𝒕𝒉𝒆 𝒗𝒂𝒍𝒖𝒆 𝒊𝒏 𝑴𝑩𝑹 𝒊𝒏𝒕𝒐 𝒕𝒉𝒆 𝒔𝒆𝒍𝒆𝒄𝒕𝒆𝒅 𝒎𝒆𝒎𝒐𝒓𝒚 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓. 𝑫𝒖𝒓𝒊𝒏𝒈 𝒕𝒉𝒆 𝒓𝒆𝒔𝒕𝒐𝒓𝒆 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏, 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕𝒔 𝒐𝒇 𝑴𝑨𝑹 𝒂𝒏𝒅 𝑴𝑩𝑹 𝒎𝒖𝒔𝒕 𝒓𝒆𝒎𝒂𝒊𝒏 𝒖𝒏𝒄𝒉𝒂𝒏𝒈𝒆𝒅.

𝑾𝒓𝒊𝒕𝒆 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏

𝑾𝒓𝒊𝒕𝒆 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒊𝒆𝒔 𝑪𝒐𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒆𝒅 𝒃𝒚 𝑺𝒆𝒎𝒊𝒄𝒐𝒏𝒅𝒖𝒄𝒕𝒐𝒓 𝑰𝑪𝒔

1. 𝑻𝒓𝒂𝒏𝒔𝒇𝒆𝒓 𝒕𝒉𝒆 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒃𝒊𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒆𝒍𝒆𝒄𝒕𝒆𝒅 𝒘𝒐𝒓𝒅 𝒊𝒏𝒕𝒐 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒍𝒊𝒏𝒆𝒔 𝒐𝒇 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒃𝒖𝒔 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝑴𝑨𝑹.

2.𝑻𝒓𝒂𝒏𝒔𝒇𝒆𝒓 𝒕𝒉𝒆 𝒅𝒂𝒕𝒂 𝒃𝒊𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒘𝒐𝒓𝒅 𝒊𝒏𝒕𝒐 𝒕𝒉𝒆 𝒅𝒂𝒕𝒂 𝒍𝒊𝒏𝒆𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒅𝒂𝒕𝒂 𝒃𝒖𝒔 𝒊𝒏𝒕𝒐 𝑴𝑩𝑹.

3.𝑨𝒄𝒕𝒊𝒗𝒂𝒕𝒆 𝒕𝒉𝒆 𝒘𝒓𝒊𝒕𝒆 𝒄𝒐𝒏𝒕𝒓𝒐𝒍 𝒖𝒏𝒊𝒕.



𝑾𝒓𝒊𝒕𝒆 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒊𝒆𝒔 𝑪𝒐𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒆𝒅 𝒃𝒚 𝑴𝒂𝒈𝒏𝒆𝒕𝒊𝒄 𝑪𝒐𝒓𝒆



𝑨 𝒘𝒓𝒊𝒕𝒆 𝒄𝒐𝒏𝒕𝒓𝒐𝒍 𝒊𝒏𝒑𝒖𝒕 𝒂𝒑𝒑𝒍𝒊𝒆𝒅 𝒕𝒐 𝒂 𝒎𝒂𝒈𝒏𝒆𝒕𝒊𝒄-𝒄𝒐𝒓𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒄𝒂𝒖𝒔𝒆𝒔 𝒂 𝒕𝒓𝒂𝒏𝒔𝒇𝒆𝒓 𝒐𝒇 𝒊𝒏𝒇𝒐𝒓𝒎𝒂𝒕𝒊𝒐𝒏. 𝑻𝒐 𝒕𝒓𝒂𝒏𝒔𝒇𝒆𝒓 𝒏𝒆𝒘 𝒊𝒏𝒇𝒐𝒓𝒎𝒂𝒕𝒊𝒐𝒏 𝒊𝒏𝒕𝒐 𝒂 𝒔𝒆𝒍𝒆𝒄𝒕𝒆𝒅 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓, 𝒕𝒉𝒆 𝒐𝒍𝒅 𝒊𝒏𝒇𝒐𝒓𝒎𝒂𝒕𝒊𝒐𝒏 𝒎𝒖𝒔𝒕 𝒇𝒊𝒓𝒔𝒕 𝒃𝒆 𝒆𝒓𝒂𝒔𝒆𝒅 𝒃𝒚 𝒄𝒍𝒆𝒂𝒓𝒊𝒏𝒈 𝒂𝒍𝒍 𝒕𝒉𝒆 𝒃𝒊𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒘𝒐𝒓𝒅 𝒕𝒐 0. 𝑨𝒇𝒕𝒆𝒓 𝒕𝒉𝒊𝒔 𝒅𝒐𝒏𝒆, 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕 𝒐𝒇 𝒕𝒉𝒆 𝑴𝑩𝑹 𝒄𝒂𝒏 𝒃𝒆 𝒕𝒓𝒂𝒏𝒔𝒇𝒆𝒓𝒓𝒆𝒅 𝒕𝒐 𝒕𝒉𝒆 𝒔𝒆𝒍𝒆𝒄𝒕𝒆𝒅 𝒘𝒐𝒓𝒅. 𝑴𝑨𝑹 𝒎𝒖𝒔𝒕 𝒏𝒐𝒕 𝒄𝒉𝒂𝒏𝒈𝒆 𝒅𝒖𝒓𝒊𝒏𝒈 𝒕𝒉𝒆 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒕𝒐 𝒆𝒏𝒔𝒖𝒓𝒆 𝒕𝒉𝒂𝒕 𝒕𝒉𝒆 𝒔𝒂𝒎𝒆 𝒔𝒆𝒍𝒆𝒄𝒕𝒆𝒅 𝒘𝒐𝒓𝒅 𝒕𝒉𝒂𝒕 𝒊𝒔 𝒄𝒍𝒆𝒂𝒓𝒆𝒅 𝒊𝒔 𝒕𝒉𝒆 𝒐𝒏𝒆 𝒕𝒉𝒂𝒕 𝒓𝒆𝒄𝒆𝒊𝒗𝒆𝒔 𝒕𝒉𝒆 𝒏𝒆𝒘 𝒊𝒏𝒇𝒐𝒓𝒎𝒂𝒕𝒊𝒐𝒏.

𝑾𝒐𝒓𝒅𝒔, 𝑩𝒚𝒕𝒆𝒔 𝒂𝒏𝒅 𝑩𝒊𝒕𝒔

8 𝒃𝒊𝒕𝒔=1 𝒃𝒚𝒕𝒆.

16 𝒃𝒊𝒕𝒔 𝒐𝒓 2 𝒃𝒚𝒕𝒆𝒔 →𝑯𝒂𝒍𝒇 𝑾𝒐𝒓𝒅.

32 𝒃𝒊𝒕𝒔 𝒐𝒓 4 𝒃𝒚𝒕𝒆𝒔→𝑺𝒊𝒏𝒈𝒍𝒆 𝑾𝒐𝒓𝒅 /𝑭𝒖𝒍𝒍 𝑾𝒐𝒓𝒅.

64 𝒃𝒊𝒕𝒔 𝒐𝒓 8 𝒃𝒚𝒕𝒆𝒔→𝑫𝒐𝒖𝒃𝒍𝒆 𝑾𝒐𝒓𝒅.

128 𝒃𝒊𝒕𝒔 𝒐𝒓 16 𝒃𝒚𝒕𝒆𝒔→𝑸𝒖𝒂𝒅 𝑾𝒐𝒓𝒅.

𝑵𝒐𝒓𝒎𝒂𝒍𝒍𝒚, 1 𝒘𝒐𝒓𝒅 𝒐𝒓 𝒂 𝒘𝒐𝒓𝒅 𝒓𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒔 16 𝒃𝒊𝒕𝒔 𝒊𝒏 𝒓𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒂𝒕𝒊𝒐𝒏.

𝑫𝒂𝒕𝒂 𝑶𝒑𝒆𝒓𝒂𝒏𝒅𝒔

𝑺𝒖𝒑𝒑𝒐𝒔𝒆 𝒘𝒆 𝒉𝒂𝒗𝒆:

𝒊𝒏𝒕 𝒂 = 10;

𝒊𝒏𝒕 𝒃=20;

𝒊𝒏𝒕 𝒄=𝒃;

𝑯𝒆𝒓𝒆,𝒂,𝒃 ,𝒄 𝒂𝒓𝒆 𝒂𝒍𝒍 𝒐𝒑𝒆𝒓𝒂𝒏𝒅𝒔 𝒕𝒉𝒂𝒕 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒇𝒖𝒓𝒕𝒉𝒆𝒓 𝒖𝒔𝒆𝒅 𝒇𝒐𝒓 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒔𝒖𝒄𝒉 𝒂𝒔 𝒊𝒏𝒕 𝒔𝒖𝒎=𝒂+𝒃.

𝑻𝒉𝒆 𝒐𝒑𝒆𝒓𝒂𝒏𝒅𝒔 𝒂𝒓𝒆 𝒕𝒉𝒐𝒔𝒆 𝒗𝒂𝒓𝒊𝒂𝒃𝒍𝒆𝒔 𝒕𝒉𝒂𝒕 𝒂𝒓𝒆 𝒘𝒐𝒓𝒌𝒆𝒅 𝒃𝒚 𝒐𝒑𝒆𝒓𝒂𝒕𝒐𝒓 𝒕𝒐 𝒑𝒓𝒐𝒅𝒖𝒄𝒆 𝒂 𝒓𝒆𝒔𝒖𝒍𝒕 𝒂𝒏𝒅 𝒔𝒖𝒄𝒉 𝒂𝒅𝒅𝒓𝒆𝒔𝒔𝒆𝒔 𝒐𝒇 𝒐𝒑𝒆𝒓𝒂𝒏𝒅𝒔 𝒂𝒓𝒆 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝒅𝒂𝒕𝒂 𝒐𝒑𝒆𝒓𝒂𝒏𝒅𝒔 𝒔𝒆𝒄𝒕𝒊𝒐𝒏 𝒐𝒇 𝒎𝒆𝒎𝒐𝒓𝒚.

𝑯𝒆𝒏𝒄𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒂𝒏𝒅 𝒎𝒆𝒎𝒐𝒓𝒚 𝒃𝒖𝒇𝒇𝒆𝒓 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒘𝒐𝒓𝒌 𝒘𝒊𝒕𝒉 𝒕𝒉𝒐𝒔𝒆 𝒅𝒂𝒕𝒂 𝒐𝒑𝒆𝒓𝒂𝒏𝒅𝒔 𝒘𝒉𝒊𝒍𝒆 𝑹𝑨𝑴 𝒊𝒔 𝒊𝒏 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏.



𝑨𝒏𝒅 𝑴𝑩𝑹 𝒘𝒊𝒍𝒍 𝒉𝒐𝒍𝒅 𝒕𝒉𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒊𝒏 𝒘𝒐𝒓𝒅 𝒓𝒆𝒂𝒅 𝒇𝒓𝒐𝒎 𝒐𝒓 𝒘𝒓𝒊𝒕𝒕𝒆𝒏 𝒕𝒐 𝒎𝒆𝒎𝒐𝒓𝒚 𝒘𝒉𝒊𝒍𝒆 𝒊𝒏 𝒘𝒆 𝒑𝒓𝒐𝒄𝒆𝒔𝒔.

𝑺𝑻𝑬𝑷 𝑩𝒀 𝑺𝑻𝑬𝑷 𝑷𝑹𝑶𝑪𝑬𝑺𝑺

1. 𝑯𝒊𝒈𝒉 𝒍𝒆𝒗𝒆𝒍 𝒑𝒓𝒐𝒈𝒓𝒂𝒎𝒎𝒊𝒏𝒈 𝒍𝒂𝒏𝒈𝒖𝒂𝒈𝒆 𝒄𝒐𝒏𝒗𝒆𝒓𝒕𝒆𝒅 𝒕𝒐 𝒑𝒓𝒐𝒈𝒓𝒂𝒎𝒎𝒊𝒏𝒈 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔 𝒃𝒚 𝒂𝒏 𝒂𝒔𝒔𝒆𝒎𝒃𝒍𝒆𝒓.

2. 𝑻𝒉𝒆𝒔𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔 𝒂𝒓𝒆 𝒑𝒓𝒐𝒗𝒊𝒅𝒆𝒅 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒃𝒚 𝑷𝒓𝒐𝒈𝒓𝒂𝒎 𝑪𝒐𝒖𝒏𝒕𝒆𝒓.

3. 𝑻𝒉𝒆 𝒐𝒑𝒆𝒓𝒂𝒏𝒅 𝒅𝒂𝒕𝒂 𝒈𝒆𝒕𝒔 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑫𝒂𝒕𝒂 𝑶𝒑𝒆𝒓𝒂𝒏𝒅 𝒔𝒆𝒄𝒕𝒊𝒐𝒏 𝒂𝒔 𝒔𝒉𝒐𝒘𝒏 𝒂𝒃𝒐𝒗𝒆 𝒂𝒏𝒅 𝑴𝑨𝑹 𝒘𝒊𝒍𝒍 𝒉𝒐𝒍𝒅 𝒕𝒉𝒆 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒂𝒏𝒅 𝑴𝑩𝑹 𝒘𝒊𝒍𝒍 𝒉𝒐𝒍𝒅 𝒕𝒉𝒆 𝒅𝒂𝒕𝒂 𝒊.𝒆., 𝒄𝒐𝒏𝒕𝒆𝒏𝒕 𝒐𝒇 𝒕𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒊𝒏 𝒘𝒐𝒓𝒅 𝒘𝒉𝒊𝒍𝒆 𝒘𝒆 𝒑𝒓𝒐𝒄𝒆𝒔𝒔 𝒕𝒉𝒆 𝒅𝒂𝒕𝒂.

4. 𝑻𝒉𝒆𝒓𝒆 𝒊𝒔 𝒂𝒏𝒐𝒕𝒉𝒆𝒓 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒂𝒔𝒔𝒐𝒄𝒊𝒂𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝒕𝒉𝒆 𝑪𝑷𝑼 𝒕𝒉𝒂𝒕 𝒊𝒔 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 (𝑰𝑹) 𝒘𝒉𝒊𝒄𝒉 𝒓𝒆𝒄𝒆𝒊𝒗𝒆𝒔 𝒕𝒉𝒆𝒔𝒆 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒄𝒐𝒅𝒆 𝒐𝒇 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔 𝒄𝒐𝒎𝒎𝒖𝒏𝒊𝒄𝒂𝒕𝒆𝒅 𝒕𝒉𝒓𝒐𝒖𝒈𝒉 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒃𝒖𝒔 𝒄𝒐𝒏𝒏𝒆𝒄𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝑷𝒓𝒐𝒈𝒓𝒂𝒎 𝑪𝒐𝒖𝒏𝒕𝒆𝒓 (𝑷𝑪) 𝒘𝒉𝒊𝒄𝒉 𝒉𝒐𝒍𝒅𝒔 𝒂𝒅𝒅𝒓𝒆𝒔𝒔𝒆𝒔 𝒐𝒇 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒄𝒐𝒅𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏𝒔 𝒂𝒏𝒅 𝒕𝒉𝒆 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔 𝒄𝒂𝒏 𝒃𝒆 𝒅𝒆𝒇𝒊𝒏𝒆𝒅 𝒂𝒔: 𝑨𝑫𝑫 (𝑨𝒅𝒅𝒊𝒕𝒊𝒐𝒏), 𝑺𝑼𝑩 (𝑺𝒖𝒃𝒕𝒓𝒂𝒄𝒕𝒊𝒐𝒏), 𝑴𝑼𝑳 (𝑴𝒖𝒍𝒕𝒊𝒑𝒍𝒊𝒄𝒂𝒕𝒊𝒐𝒏), 𝒆𝒕𝒄. 𝒂𝒏𝒅 𝒕𝒉𝒆 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒘𝒉𝒊𝒄𝒉 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒅𝒐𝒏𝒆 𝒘𝒊𝒕𝒉 𝒐𝒑𝒆𝒓𝒂𝒏𝒅𝒔 𝒔𝒖𝒄𝒉 𝒂𝒅𝒅𝒓𝒆𝒔𝒔𝒆𝒔 𝒊𝒔 𝒇𝒆𝒕𝒄𝒉𝒆𝒅 𝒃𝒚 𝑴𝑨𝑹 (𝑴𝒆𝒎𝒐𝒓𝒚 𝑨𝒅𝒅𝒓𝒆𝒔𝒔 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓) 𝒂𝒏𝒅 𝒂 𝒅𝒆𝒄𝒐𝒅𝒆𝒓 𝒂𝒔𝒔𝒐𝒄𝒊𝒂𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 (𝑰𝑹) 𝒔𝒖𝒑𝒑𝒍𝒊𝒆𝒔 𝒆𝒂𝒄𝒉 𝒐𝒖𝒕𝒑𝒖𝒕 𝒕𝒐 𝒕𝒉𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 .

𝑺𝒕𝒂𝒄𝒌

1. 𝑶𝒑𝒄𝒐𝒅𝒆𝒔: 𝑨𝑫𝑫, 𝑴𝑼𝑳.

2.𝑫𝒂𝒕𝒂 𝑶𝒑𝒆𝒓𝒂𝒏𝒅𝒔: 𝑫=10, 𝑩=12, 𝑪=13.

3.𝑵𝒐𝒘 𝒘𝒆 𝒉𝒂𝒗𝒆 𝒕𝒐 𝒑𝒆𝒓𝒇𝒐𝒓𝒎: (𝑪+𝑩)*𝑫.

𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏: 𝑷𝑼𝑺𝑯 𝑩



𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏: 𝑷𝑼𝑺𝑯 𝑪 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑫𝒂𝒕𝒂 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆, 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒈𝒆𝒕𝒔 𝒅𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕𝒆𝒅 (𝑺𝑷-1 = (4000-1) = 3999 𝒐𝒓 0𝒙𝑭9𝑭).

𝑵𝒐𝒘 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒆𝒙𝒆𝒄𝒖𝒕𝒆 𝒁𝒆𝒓𝒐 𝑨𝒅𝒅𝒓𝒆𝒔𝒔 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏:

𝑨𝒔 𝑨𝒅𝒅 𝒊𝒔 𝒂𝒏 𝒐𝒑𝒄𝒐𝒅𝒆 (𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒄𝒐𝒅𝒆) 𝒂𝒏𝒅 𝒕𝒉𝒆𝒏 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒈𝒆𝒏𝒆𝒓𝒂𝒕𝒆:

𝑨𝒅𝒅 𝑪,𝑩 𝒂𝒏𝒅 𝒕𝒉𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝒘𝒊𝒍𝒍 𝒈𝒆𝒕 𝒎𝒊𝒏𝒊𝒎𝒊𝒛𝒆𝒅(𝒁𝒆𝒓𝒐 𝑨𝒅𝒅𝒓𝒆𝒔𝒔).

𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏: 𝑷𝑶𝑷 𝑪 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒚



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆, 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒈𝒆𝒕𝒔 𝒊𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕𝒆𝒅 (𝑺𝑷+1 = (3999+1) = 4000 𝒐𝒓 0𝒙𝑭𝑨0)

𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏: 𝑷𝑶𝑷 𝑩 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒚



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆, 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒑𝒐𝒊𝒏𝒕𝒔 𝒂𝒕 𝒕𝒉𝒆 𝒍𝒂𝒔𝒕 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 4000, 𝑾𝒉𝒊𝒍𝒆 𝒕𝒉𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝒈𝒆𝒕𝒔 𝒄𝒐𝒎𝒑𝒍𝒆𝒕𝒆𝒅 𝒊.𝒆. 𝑨𝑫𝑫 𝑪,𝑩 (=13+12)𝒂𝒏𝒅 𝒊𝒕 𝒈𝒐𝒆𝒔 𝒕𝒐 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒂𝒔𝒔𝒐𝒄𝒊𝒂𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝒊𝒕𝒔 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒂𝒏𝒅 𝒅𝒆𝒄𝒐𝒅𝒆𝒓 𝒂𝒔𝒔𝒐𝒄𝒊𝒂𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒐𝒇 𝑪𝑷𝑼 𝒑𝒓𝒐𝒗𝒊𝒅𝒆𝒔 𝒕𝒉𝒆 𝒐𝒖𝒕 𝒑𝒖𝒕 , 𝒔𝒂𝒚 𝒐𝒖𝒕𝒑𝒖𝒕 = 𝑹𝑬𝑺(=25) . 𝑻𝒉𝒆 𝒗𝒂𝒍𝒖𝒆 𝒈𝒆𝒕𝒔 𝒂𝒈𝒂𝒊𝒏 𝒔𝒕𝒐𝒓𝒆𝒅 𝒂𝒕 𝑫𝒂𝒕𝒂 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓.



𝑨𝒏𝒅 𝒇𝒓𝒐𝒎 𝑫𝒂𝒕𝒂 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒊𝒕 𝒂𝒈𝒂𝒊𝒏 𝑷𝒖𝒔𝒉𝒆𝒅 𝒊𝒏𝒕𝒐 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒇𝒐𝒓 𝒇𝒖𝒓𝒕𝒉𝒆𝒓 𝒑𝒓𝒐𝒄𝒆𝒔𝒔.



𝑵𝒐𝒘 𝑫𝒂𝒕𝒂 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒄𝒐𝒏𝒕𝒂𝒊𝒏𝒔 𝑫.



𝑺𝑻𝑨𝑪𝑲 𝑶𝑷𝑬𝑹𝑨𝑻𝑰𝑶𝑵 𝑷𝑼𝑺𝑯 𝑫 𝑺𝑻𝑶𝑹𝑬𝑫 𝑰𝑵 𝑫𝑨𝑻𝑨 𝑹𝑬𝑮𝑰𝑺𝑻𝑬𝑹.



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆, 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒈𝒆𝒕𝒔 𝒅𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕𝒆𝒅 (𝑺𝑷-1 = (4000-1) = 3999 𝒐𝒓 0𝒙𝑭9𝑭).

𝑵𝒐𝒘 𝑫𝒂𝒕𝒂 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒘𝒊𝒍𝒍 𝒄𝒐𝒏𝒕𝒂𝒊𝒏 𝑴𝑼𝑳 𝒐𝒑𝒄𝒐𝒅𝒆.



𝑵𝒐𝒘 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒆𝒙𝒆𝒄𝒖𝒕𝒆 𝒁𝒆𝒓𝒐 𝑨𝒅𝒅𝒓𝒆𝒔𝒔 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏:

𝑨𝒔 𝑴𝑼𝑳 𝒊𝒔 𝒂𝒏 𝒐𝒑𝒄𝒐𝒅𝒆 (𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒄𝒐𝒅𝒆) 𝒂𝒏𝒅 𝒕𝒉𝒆𝒏 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒈𝒆𝒏𝒆𝒓𝒂𝒕𝒆:

𝑴𝑼𝑳 𝑫,𝑹𝑬𝑺 𝒂𝒏𝒅 𝒕𝒉𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝒘𝒊𝒍𝒍 𝒈𝒆𝒕 𝒎𝒊𝒏𝒊𝒎𝒊𝒛𝒆𝒅(𝒁𝒆𝒓𝒐 𝑨𝒅𝒅𝒓𝒆𝒔𝒔).

𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏: 𝑷𝑶𝑷 𝑫 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒚



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆, 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒈𝒆𝒕𝒔 𝒊𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕𝒆𝒅 (𝑺𝑷+1 = (3999+1) = 4000 𝒐𝒓 0𝒙𝑭𝑨0).

𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏: 𝑷𝑶𝑷 𝑹𝑬𝑺 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒚



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆, 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒑𝒐𝒊𝒏𝒕𝒔 𝒂𝒕 𝒕𝒉𝒆 𝒍𝒂𝒔𝒕 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 4000, 𝑾𝒉𝒊𝒍𝒆 𝒕𝒉𝒆 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝒈𝒆𝒕𝒔 𝒄𝒐𝒎𝒑𝒍𝒆𝒕𝒆𝒅 𝒊.𝒆., 𝑴𝑼𝑳 𝑫, 𝑹𝑬𝑺 (=10×25=250)𝒂𝒏𝒅 𝒊𝒕 𝒈𝒐𝒆𝒔 𝒕𝒐 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒂𝒔𝒔𝒐𝒄𝒊𝒂𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝒊𝒕𝒔 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒂𝒏𝒅 𝒅𝒆𝒄𝒐𝒅𝒆𝒓 𝒂𝒔𝒔𝒐𝒄𝒊𝒂𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒐𝒇 𝑪𝑷𝑼 𝒑𝒓𝒐𝒗𝒊𝒅𝒆𝒔 𝒕𝒉𝒆 𝒐𝒖𝒕𝒑𝒖𝒕. 𝑻𝒉𝒆 𝒗𝒂𝒍𝒖𝒆 𝒈𝒆𝒕𝒔 𝒂𝒈𝒂𝒊𝒏 𝒔𝒕𝒐𝒓𝒆𝒅 𝒂𝒕 𝑫𝒂𝒕𝒂 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒂𝒏𝒅 𝒕𝒉𝒆𝒏 𝒊𝒕 𝒈𝒆𝒕𝒔 𝒊𝒏𝒕𝒆𝒓𝒑𝒓𝒆𝒕𝒆𝒅 𝒕𝒐 𝒖𝒔𝒆𝒓.

𝑸)𝑾𝒉𝒂𝒕 𝒘𝒊𝒍𝒍 𝒉𝒂𝒑𝒑𝒆𝒏 𝒘𝒉𝒆𝒏 𝒔𝒕𝒂𝒄𝒌 𝒈𝒆𝒕𝒔 𝑬𝒎𝒑𝒕𝒚 𝒐𝒓 𝑼𝑵𝑫𝑬𝑹𝑭𝑳𝑶𝑾?

𝑨𝑵𝑺: 𝑻𝒉𝒆𝒓𝒆 𝒂𝒓𝒆 𝒕𝒘𝒐 𝒇𝒍𝒂𝒈𝒔 𝒘𝒐𝒓𝒌𝒊𝒏𝒈 𝒕𝒐𝒈𝒆𝒕𝒉𝒆𝒓:

1.𝑭𝑼𝑳𝑳

2.𝑬𝑴𝑷𝑻𝒀

𝑾𝒉𝒊𝒍𝒆 𝒔𝒕𝒂𝒄𝒌 𝒈𝒆𝒕𝒔 𝒆𝒎𝒑𝒕𝒚, 𝒔𝒕𝒂𝒄𝒌 𝒑𝒐𝒊𝒏𝒕𝒆𝒓 𝒘𝒊𝒍𝒍 𝒃𝒆𝒄𝒐𝒎𝒆 0. 𝑵𝒐𝒘, 𝒂𝒔 𝒔𝒐𝒐𝒏 𝒂𝒔 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒃𝒆𝒄𝒐𝒎𝒆𝒔 0, 𝑭𝑼𝑳𝑳 𝒇𝒍𝒂𝒈 𝒘𝒊𝒍𝒍 𝒃𝒆𝒄𝒐𝒎𝒆 0 𝒊.𝒆., 𝒇𝒂𝒍𝒔𝒆, 𝒂𝒏𝒅 𝑬𝑴𝑷𝑻𝒀 𝒇𝒍𝒂𝒈 𝒘𝒊𝒍𝒍 𝒃𝒆𝒄𝒐𝒎𝒆 1 𝒊.𝒆., 𝒕𝒓𝒖𝒆.

𝑰𝒕 𝒄𝒂𝒏 𝒂𝒍𝒔𝒐 𝒃𝒆 𝒓𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒆𝒅 𝒂𝒔:

𝑰𝒇 (𝑺𝑷 == 0){
𝑬𝑴𝑷𝑻𝒀 ←1
𝑭𝑼𝑳𝑳 ←0 
}

𝑸) 𝑾𝒉𝒂𝒕 𝒘𝒊𝒍𝒍 𝒉𝒂𝒑𝒑𝒆𝒏 𝒘𝒉𝒆𝒏 𝒔𝒕𝒂𝒄𝒌 𝒈𝒆𝒕𝒔 𝑭𝒖𝒍𝒍 𝒐𝒓 𝑶𝒗𝒆𝒓𝒇𝒍𝒐𝒘?

𝑨𝑵𝑺:𝑺𝒖𝒑𝒑𝒐𝒔𝒆 𝒘𝒆 𝒉𝒂𝒗𝒆 𝒔𝒕𝒂𝒄𝒌 𝒄𝒐𝒏𝒕𝒂𝒊𝒏𝒔 64-𝒘𝒐𝒓𝒅 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒍𝒐𝒐𝒌𝒔 𝒍𝒊𝒌𝒆:



𝑳𝒆𝒕𝒔 𝒔𝒂𝒚 0 𝒊𝒔 𝒕𝒐𝒑 𝒕𝒉𝒆𝒏 𝑷𝒖𝒔𝒉 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒐𝒄𝒄𝒖𝒓𝒔: 𝑺𝑷 = 𝑺𝑷+1 (𝑰𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓) 𝒂𝒏𝒅 𝑷𝑶𝑷 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒐𝒄𝒄𝒖𝒓𝒔: 𝑺𝑷 = 𝑺𝑷-1 (𝑫𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓). 63 𝒊𝒔 𝒕𝒉𝒆 𝒍𝒂𝒔𝒕 𝒃𝒊𝒕 𝒓𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝑩𝒊𝒏𝒂𝒓𝒚 𝒅𝒊𝒈𝒊𝒕𝒔 111111 (𝑺𝒊𝒙 𝑶𝒏𝒆𝒔=𝑺𝒊𝒙 𝑩𝒊𝒕𝒔). 𝑻𝒉𝒆𝒏 𝒕𝒉𝒆 𝒕𝒐𝒑 0 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒓𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒆𝒅 𝒊𝒏 6 𝒃𝒊𝒕𝒔 𝒐𝒓 6 𝒛𝒆𝒓𝒐𝒆𝒔 [000 000].



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆 𝒂𝒕 64 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒃𝒆 1 000 000 𝒊.𝒆.1 𝒂𝒏𝒅 𝒔𝒊𝒙 𝒛𝒆𝒓𝒐𝒆𝒔 .

𝑯𝒆𝒏𝒄𝒆 1 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒅𝒊𝒔𝒄𝒂𝒓𝒅𝒆𝒅 𝒂𝒏𝒅 𝒔𝒊𝒙 𝒛𝒆𝒓𝒐𝒆𝒔 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒂𝒄𝒄𝒆𝒑𝒕𝒆𝒅.

𝑺𝒊𝒙 𝒛𝒆𝒓𝒐𝒆𝒔 𝒓𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕 𝒛𝒆𝒓𝒐 𝒕𝒉 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 𝒊.𝒆., 𝑻𝒐𝒑 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌, 𝒘𝒉𝒆𝒓𝒆 𝒕𝒉𝒆 𝒍𝒂𝒔𝒕 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒊𝒏𝒔𝒆𝒓𝒕𝒆𝒅 𝒘𝒉𝒆𝒏 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒈𝒆𝒕𝒔 𝒇𝒊𝒍𝒍𝒆𝒅.

𝑻𝒉𝒊𝒔 𝒕𝒆𝒍𝒍𝒔 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒘𝒊𝒍𝒍 𝒃𝒆𝒄𝒐𝒎𝒆 𝒛𝒆𝒓𝒐 𝒂𝒈𝒂𝒊𝒏 𝒂𝒏𝒅 𝒊𝒇 𝒔𝒕𝒂𝒄𝒌 𝒑𝒐𝒊𝒏𝒕𝒆𝒓 𝒃𝒆𝒄𝒐𝒎𝒆𝒔 𝒛𝒆𝒓𝒐 𝒉𝒆𝒓𝒆:

𝑭𝒖𝒍𝒍→1(𝒕𝒓𝒖𝒆)
𝑬𝒎𝒑𝒕𝒚→0 (𝑭𝒂𝒍𝒔𝒆).

𝒊.𝒆.,

𝑰𝒇 (𝑺𝑷 == 0){
𝑭𝑼𝑳𝑳 ←1
𝑬𝑴𝑷𝑻𝒀 ←0 
}

𝑵𝒐𝒕𝒆: 𝑭𝒖𝒍𝒍 𝒂𝒏𝒅 𝑬𝒎𝒑𝒕𝒚 𝒊𝒔 𝑭𝒍𝒊𝒑 𝑭𝒍𝒐𝒑 𝒄𝒊𝒓𝒄𝒖𝒊𝒕, 𝒘𝒉𝒆𝒏 𝑭𝒖𝒍𝒍 𝒈𝒆𝒏𝒆𝒓𝒂𝒕𝒆𝒔 0 (𝒃𝒆𝒄𝒐𝒎𝒆𝒔 𝑶𝒇𝒇) 𝒂𝒏𝒅 𝒐𝒕𝒉𝒆𝒓 𝑬𝒎𝒑𝒕𝒚 𝒈𝒆𝒏𝒆𝒓𝒂𝒕𝒆𝒔 1 (𝒃𝒆𝒄𝒐𝒎𝒆𝒔 𝑶𝑵) 𝒂𝒏𝒅 𝒗𝒊𝒄𝒆 𝒗𝒆𝒓𝒔𝒂. 𝑻𝒉𝒂𝒕 𝒊𝒔 𝒘𝒉𝒂𝒕 𝒂 𝑭𝒍𝒊𝒑 𝑭𝒍𝒐𝒑 𝑪𝒊𝒓𝒄𝒖𝒊𝒕 𝒅𝒐𝒆𝒔.

𝑺𝑼𝑷𝑷𝑶𝑺𝑬 𝑰𝑭 𝑰𝑻 𝑰𝑺 𝑶𝑷𝑷𝑶𝑺𝑰𝑻𝑬 𝑻𝑶𝑷 𝑷𝑶𝑰𝑵𝑻𝑺 𝑻𝑶 𝑳𝒂𝒔𝒕 𝑰𝒏𝒅𝒆𝒙 𝒔𝒂𝒚 63 𝑻𝑯𝑬𝑵:

𝑷𝒖𝒔𝒉 = 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 (𝑺𝑷) -1(𝑫𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕)

𝑷𝒐𝒑 = 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 (𝑺𝑷) +1(𝑰𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕)

𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆 𝒘𝒉𝒆𝒏 𝒊𝒕 𝒓𝒆𝒂𝒄𝒉𝒆𝒔 0, 𝒏𝒆𝒙𝒕 𝒅𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒘𝒊𝒍𝒍 𝒄𝒂𝒖𝒔𝒆 : -1 , 𝑹𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 6 𝒃𝒊𝒕 𝒐𝒇 1 = 000 001 , 𝑶𝒏𝒆’𝒔 𝒄𝒐𝒎𝒑𝒍𝒆𝒎𝒆𝒏𝒕 𝒐𝒇 1 = 111 110 𝒂𝒏𝒅 𝑻𝒘𝒐’𝒔 𝒄𝒐𝒎𝒑𝒍𝒆𝒎𝒆𝒏𝒕 (111 110 +1) = 111 111. 𝑨𝒏𝒅 𝒘𝒆 𝒌𝒏𝒐𝒘 111 111 𝒊𝒔 63 , 𝒉𝒆𝒏𝒄𝒆 𝒂𝒈𝒂𝒊𝒏 𝒔𝒕𝒂𝒄𝒌 𝒘𝒊𝒍𝒍 𝒑𝒐𝒊𝒏𝒕 𝒂𝒕 63.

𝑨𝒈𝒂𝒊𝒏, 𝒊𝒕 𝒔𝒂𝒕𝒊𝒔𝒇𝒊𝒆𝒔:

𝑰𝒇 (𝑺𝑷 == 0){
𝑭𝑼𝑳𝑳 ←1
𝑬𝑴𝑷𝑻𝒀 ←0 
}

𝑵𝒐𝒕𝒆: - 𝑰𝒕 𝒅𝒐𝒆𝒔 𝒏𝒐𝒕 𝒎𝒂𝒕𝒕𝒆𝒓 𝒕𝒉𝒂𝒕 𝑺𝒕𝒂𝒄𝒌 𝑷𝒐𝒊𝒏𝒕𝒆𝒓 𝒘𝒊𝒍𝒍 𝒂𝒍𝒘𝒂𝒚𝒔 𝒅𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒐𝒓 𝒂𝒍𝒘𝒂𝒚𝒔 𝒊𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕, 𝒊𝒕 𝒅𝒆𝒑𝒆𝒏𝒅𝒔 𝒖𝒑𝒐𝒏 𝒐𝒖𝒓 𝒓𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝒐𝒖𝒓 𝑴𝒆𝒎𝒐𝒓𝒚, 𝒘𝒉𝒆𝒕𝒉𝒆𝒓 𝒘𝒆 𝒂𝒓𝒆 𝒑𝒐𝒊𝒏𝒕𝒊𝒏𝒈 𝒔𝒕𝒂𝒄𝒌 𝒂𝒕 𝒇𝒊𝒓𝒔𝒕 𝒐𝒓 𝒍𝒂𝒔𝒕 𝒊𝒏𝒅𝒆𝒙 𝒂𝒅𝒅𝒓𝒆𝒔𝒔.

𝑨𝒈𝒂𝒊𝒏, 𝒊𝒇 𝒘𝒆 𝒏𝒐𝒕𝒊𝒄𝒆, 𝑺𝒂𝒎𝒆 𝒘𝒂𝒚 𝑨 𝑹𝑬𝑮𝑰𝑺𝑻𝑬𝑹 𝑺𝑻𝑨𝑪𝑲 𝒘𝒐𝒓𝒌𝒔 𝒍𝒊𝒌𝒆 𝑴𝑬𝑴𝑶𝑹𝒀 𝑺𝑻𝑨𝑪𝑲 𝒂𝒔 𝑹𝒆𝒈𝒊𝒔𝒕𝒆𝒓𝒔 𝒂𝒓𝒆 𝒂𝒍𝒔𝒐 𝒂 𝒎𝒆𝒎𝒐𝒓𝒚 (𝒔𝒎𝒂𝒍𝒍𝒆𝒔𝒕 𝒅𝒂𝒕𝒂 𝒔𝒕𝒐𝒓𝒂𝒈𝒆 𝒖𝒏𝒊𝒕).

𝑪. 𝑨𝒑𝒑𝒍𝒊𝒄𝒂𝒕𝒊𝒐𝒏𝒔 𝑩𝒂𝒔𝒆𝒅 𝑶𝒏 𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏:

1. 𝑩𝒂𝒍𝒂𝒏𝒄𝒊𝒏𝒈 𝒐𝒇 𝑺𝒚𝒎𝒃𝒐𝒍𝒔.

2. 𝑰𝒏𝒇𝒊𝒙 𝒕𝒐 𝒑𝒐𝒔𝒕 𝒇𝒊𝒙 𝒄𝒐𝒏𝒗𝒆𝒓𝒔𝒊𝒐𝒏.

3. 𝑬𝒗𝒂𝒍𝒖𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝒑𝒐𝒔𝒕-𝒇𝒊𝒙 𝒆𝒙𝒑𝒓𝒆𝒔𝒔𝒊𝒐𝒏.

4. 𝑰𝒎𝒑𝒍𝒆𝒎𝒆𝒏𝒕𝒊𝒏𝒈 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏 𝒄𝒂𝒍𝒍 (𝒊𝒏𝒄𝒍𝒖𝒅𝒊𝒏𝒈 𝒓𝒆𝒄𝒖𝒓𝒔𝒊𝒐𝒏).

5. 𝑭𝒊𝒏𝒅𝒊𝒏𝒈 𝒐𝒇 𝒔𝒑𝒂𝒏𝒔 𝒊𝒏 𝑺𝒕𝒐𝒄𝒌 𝑴𝒂𝒓𝒌𝒆𝒕.

6. 𝑷𝒂𝒈𝒆 𝑽𝒊𝒔𝒊𝒕𝒆𝒅 𝒉𝒊𝒔𝒕𝒐𝒓𝒚 𝒊𝒏 𝒂 𝑾𝒆𝒃 𝑩𝒓𝒐𝒘𝒔𝒆𝒓 [𝑯𝒊𝒔𝒕𝒐𝒓𝒚 𝑺𝒆𝒄𝒕𝒊𝒐𝒏 𝒐𝒇 𝑾𝒆𝒃 𝑩𝒓𝒐𝒘𝒔𝒆𝒓].

7. 𝑩𝒂𝒄𝒌 𝑩𝒖𝒕𝒕𝒐𝒏𝒔 𝒊𝒏 𝑯𝑻𝑴𝑳. 𝑻𝒉𝒂𝒕 𝒊𝒔 𝒂𝒍𝒍 𝒑𝒂𝒈𝒆𝒔 𝒊𝒏 𝒘𝒆𝒃 𝒔𝒊𝒕𝒆 𝒂𝒓𝒆 𝒔𝒕𝒐𝒓𝒆𝒅 𝒍𝒊𝒌𝒆 𝑺𝒕𝒂𝒄𝒌𝒔 𝒂𝒏𝒅 𝒃𝒂𝒄𝒌 𝒃𝒖𝒕𝒕𝒐𝒏 𝒉𝒆𝒍𝒑𝒔 𝒕𝒉𝒆 𝒑𝒂𝒈𝒆𝒔 𝒕𝒐 𝒑𝒐𝒑 𝒐𝒖𝒕 𝒕𝒉𝒆 𝑷𝒂𝒈𝒆 𝒗𝒊𝒔𝒊𝒕𝒆𝒅 𝒂𝒏𝒅 𝑷𝒖𝒔𝒉 𝒊𝒏 𝒕𝒉𝒆 𝑳𝒂𝒔𝒕 𝑷𝒂𝒈𝒆 𝒗𝒊𝒔𝒊𝒕𝒆𝒅 [𝑳𝒂𝒔𝒕 𝒊𝒏 𝑭𝒊𝒓𝒔𝒕 𝑶𝒖𝒕].

8. 𝑼𝒏𝒅𝒐 𝒔𝒆𝒒𝒖𝒆𝒏𝒄𝒆 𝒊𝒏 𝒂 𝑻𝒆𝒙𝒕 𝒆𝒅𝒊𝒕𝒐𝒓.

9. 𝑴𝒂𝒕𝒄𝒉𝒊𝒏𝒈 𝑻𝒂𝒈𝒔 𝒊𝒏 𝑯𝑻𝑴𝑳 𝒂𝒏𝒅 𝑿𝑯𝑻𝑴𝑳.

10. 𝑰𝒏 𝒄𝒓𝒐𝒔𝒔 𝒑𝒍𝒂𝒕𝒇𝒐𝒓𝒎 𝒂𝒑𝒑𝒍𝒊𝒄𝒂𝒕𝒊𝒐𝒏 𝒘𝒆 𝒄𝒂𝒏 𝒔𝒆𝒕 𝒘𝒊𝒏𝒅𝒐𝒘𝒔 𝒐𝒓 𝒑𝒂𝒈𝒆𝒔 𝒊𝒏 𝑺𝒕𝒂𝒄𝒌 𝑭𝒐𝒓𝒎𝒂𝒕 𝒇𝒐𝒓 𝒏𝒂𝒗𝒊𝒈𝒂𝒕𝒊𝒐𝒏 𝒂𝒏𝒅 𝒘𝒉𝒆𝒏 𝒘𝒆 𝒏𝒂𝒗𝒊𝒈𝒂𝒕𝒆 𝒕𝒐 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒕 𝒑𝒂𝒈𝒆𝒔 𝒊𝒏 𝒄𝒓𝒐𝒔𝒔 𝒑𝒍𝒂𝒕𝒇𝒐𝒓𝒎 𝒂𝒑𝒑𝒍𝒊𝒄𝒂𝒕𝒊𝒐𝒏𝒔 (𝒂𝒏𝒅𝒓𝒐𝒊𝒅, 𝒊𝑶𝑺), 𝒕𝒉𝒆 𝒑𝒖𝒔𝒉 𝒂𝒏𝒅 𝒑𝒐𝒑 𝒂𝒓𝒆 𝒃𝒆𝒊𝒏𝒈 𝒊𝒎𝒑𝒍𝒆𝒎𝒆𝒏𝒕𝒆𝒅.

𝑺𝒕𝒂𝒄𝒌 𝑽𝒔 𝑯𝒆𝒂𝒑𝒔

𝑳𝒊𝒌𝒆 𝑺𝒕𝒂𝒄𝒌,𝑯𝒆𝒂𝒑 𝒊𝒔 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑹𝑨𝑴.

𝑺𝒖𝒑𝒑𝒐𝒔𝒆:

𝒊𝒏𝒕*𝒑=(𝒊𝒏𝒕*)𝒎𝒂𝒍𝒍𝒐𝒄(4*𝒔𝒊𝒛𝒆𝒐𝒇(𝒊𝒏𝒕));

𝑰𝒕 𝒄𝒓𝒆𝒂𝒕𝒆𝒔 𝒂 𝒔𝒑𝒂𝒄𝒆 𝒇𝒐𝒓 𝒂𝒏 𝒂𝒓𝒓𝒂𝒚 𝒐𝒇 4 𝒊𝒏𝒕𝒆𝒈𝒆𝒓𝒔.

𝑩𝒖𝒕 𝒊𝒕 𝒈𝒆𝒕 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑭𝒓𝒆𝒆 𝑴𝒆𝒎𝒐𝒓𝒚 𝒐𝒇 𝑹𝑨𝑴 𝒊.𝒆. 𝑯𝒆𝒂𝒑 𝑴𝒆𝒎𝒐𝒓𝒚.

𝑺𝒖𝒑𝒑𝒐𝒔𝒆 *𝒑 𝒉𝒐𝒍𝒅𝒔 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒅𝒅𝒓𝒆𝒔𝒔∶ 400 ,𝒊𝒕 𝒈𝒆𝒕 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝑺𝒕𝒂𝒄𝒌.

𝑻𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 400 𝒊𝒔 𝒕𝒉𝒆 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒐𝒇 𝑯𝒆𝒂𝒑 𝑴𝒆𝒎𝒐𝒓𝒚 𝒘𝒉𝒆𝒓𝒆 𝒂𝒓𝒓𝒂𝒚 𝒐𝒇 4 𝒊𝒏𝒕𝒆𝒈𝒆𝒓𝒔 𝒊𝒔 𝒔𝒕𝒐𝒓𝒆𝒅.



𝑨𝒇𝒕𝒆𝒓 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒏 𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝒇𝒊𝒏𝒊𝒔𝒉𝒆𝒅:

• 𝒑𝒐𝒊𝒏𝒕𝒆𝒓 𝒑 𝒈𝒆𝒕𝒔 𝒅𝒆𝒔𝒕𝒓𝒐𝒚𝒆𝒅 𝒊.𝒆., 𝒂𝒇𝒕𝒆𝒓 𝑺𝒕𝒂𝒄𝒌 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒆𝒗𝒆𝒓𝒚𝒕𝒉𝒊𝒏𝒈 𝒊𝒏 𝒔𝒕𝒂𝒄𝒌 𝒈𝒆𝒕𝒔 𝒑𝒐𝒑𝒑𝒆𝒅 𝒐𝒖𝒕 𝒂𝒏𝒅 𝒔𝒕𝒂𝒄𝒌 𝒈𝒆𝒕𝒔 𝒆𝒎𝒑𝒕𝒚.

• 𝑻𝒉𝒆 𝒅𝒂𝒕𝒂 𝒊𝒏 𝒉𝒆𝒂𝒑 𝒎𝒆𝒎𝒐𝒓𝒚 𝒓𝒆𝒎𝒂𝒊𝒏𝒔 𝒂𝒕 𝒕𝒉𝒆 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏. 𝑾𝒉𝒊𝒄𝒉 𝒘𝒆 𝒅𝒆𝒍𝒆𝒕𝒆 𝒎𝒂𝒏𝒖𝒂𝒍𝒍𝒚 𝒂𝒔 𝒅𝒊𝒔𝒄𝒖𝒔𝒔𝒆𝒅 𝒊𝒏 𝒂𝒓𝒓𝒂𝒚𝒔.

𝒊.𝒆.,



𝒊.𝒆., 𝒇𝒓𝒆𝒆 𝒌𝒆𝒚𝒘𝒐𝒓𝒅 𝒇𝒐𝒓 𝒎𝒂𝒍𝒍𝒐𝒄 𝒂𝒏𝒅 𝒅𝒆𝒍𝒆𝒕𝒆 𝒌𝒆𝒚𝒘𝒐𝒓𝒅 𝒇𝒐𝒓 𝒏𝒆𝒘 𝒐𝒑𝒆𝒓𝒂𝒕𝒐𝒓.

𝑺𝒐𝒎𝒆𝒕𝒊𝒎𝒆𝒔 𝒂𝒇𝒕𝒆𝒓 𝒅𝒆𝒍𝒆𝒕𝒊𝒐𝒏 𝒐𝒇 𝒅𝒂𝒕𝒂 𝒇𝒓𝒐𝒎 𝒔𝒕𝒂𝒄𝒌 𝒘𝒆 𝒅𝒐 𝒊𝒔 𝒂𝒔𝒔𝒊𝒈𝒏 𝑷 𝒕𝒐 𝑵𝑼𝑳𝑳 𝒂𝒇𝒕𝒆𝒓 𝒕𝒉𝒆 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒈𝒆𝒕𝒔 𝒐𝒗𝒆𝒓.

𝑷=𝑵𝑼𝑳𝑳 

𝑻𝒐 𝒇𝒓𝒆𝒆 𝒕𝒉𝒆 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 𝒐𝒓 𝒘𝒉𝒂𝒕 𝒔𝒐 𝒆𝒗𝒆𝒓 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝒑𝒐𝒊𝒏𝒕𝒆𝒓 𝒑 𝒗𝒂𝒓𝒊𝒂𝒃𝒍𝒆.

𝑺𝒕𝒂𝒄𝒌 𝑨𝒏𝒅 𝑺𝒕𝒂𝒕𝒊𝒄 𝑨𝒓𝒓𝒂𝒚𝒔

𝑺𝒕𝒂𝒕𝒊𝒄 𝑨𝒓𝒓𝒂𝒚𝒔 𝒂𝒓𝒆 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝒔𝒕𝒂𝒄𝒌 𝒔𝒆𝒄𝒕𝒊𝒐𝒏 𝒐𝒇 𝒎𝒆𝒎𝒐𝒓𝒚:

𝑾𝒆 𝒌𝒏𝒐𝒘 𝒂𝒓𝒓𝒂𝒚𝒔 𝒈𝒆𝒕 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝒄𝒐𝒏𝒕𝒊𝒈𝒖𝒐𝒖𝒔 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 (𝒊.𝒆., 𝒂𝒅𝒋𝒂𝒄𝒆𝒏𝒕 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏).

𝑻𝒉𝒆 𝒄𝒐𝒏𝒄𝒆𝒑𝒕 𝒉𝒆𝒓𝒆 𝒊𝒔 𝒔𝒕𝒐𝒓𝒊𝒏𝒈 𝒂𝒓𝒓𝒂𝒚’𝒔 𝒆𝒍𝒆𝒎𝒆𝒏𝒕:

𝑰𝒇 𝒂 [0] 𝒈𝒆𝒕𝒔 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏 𝒂𝒅𝒅𝒓𝒆𝒔𝒔 :1000 𝒐𝒇 𝒔𝒕𝒂𝒄𝒌

𝑻𝒉𝒆 𝒏𝒆𝒙𝒕 𝒂𝒓𝒓𝒂𝒚𝒔 𝒊𝒏𝒅𝒆𝒙 𝒘𝒊𝒍𝒍 𝒃𝒆 1001 𝒐𝒇 𝒔𝒕𝒂𝒄𝒌 𝒂𝒏𝒅 𝒏𝒐𝒕 1004 𝒐𝒓 𝒂𝒏𝒚 𝒐𝒕𝒉𝒆𝒓 𝒂𝒅𝒅𝒓𝒆𝒔𝒔. 𝑻𝒉𝒊𝒔 𝒊𝒔 𝒕𝒉𝒆 𝒄𝒐𝒏𝒄𝒆𝒑𝒕 𝒐𝒇 𝒄𝒐𝒏𝒕𝒊𝒈𝒖𝒐𝒖𝒔 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 𝒕𝒉𝒂𝒕 𝒊𝒔 𝒔𝒕𝒐𝒓𝒊𝒏𝒈 𝒊𝒏 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒅𝒋𝒂𝒄𝒆𝒏𝒕𝒍𝒚 𝒊𝒕 𝒍𝒐𝒐𝒌𝒔 𝒍𝒊𝒌𝒆:



𝑨𝒔 𝒘𝒆 𝒔𝒆𝒆 𝒃𝒐𝒕𝒉 𝒔𝒕𝒂𝒄𝒌 𝒂𝒏𝒅 𝑨𝒓𝒓𝒂𝒚𝒔 𝒂𝒓𝒆 𝒍𝒊𝒏𝒆𝒂𝒓𝒍𝒚 𝒔𝒕𝒓𝒖𝒄𝒕𝒖𝒓𝒆𝒅 , 𝒐𝒏𝒆 𝒂𝒇𝒕𝒆𝒓 𝒕𝒉𝒆 𝒐𝒕𝒉𝒆𝒓 𝒉𝒆𝒏𝒄𝒆 𝒕𝒉𝒆𝒚 𝒇𝒂𝒍𝒍 𝒊𝒏 𝒍𝒊𝒏𝒆𝒂𝒓 𝒅𝒂𝒕𝒂 𝒔𝒕𝒓𝒖𝒄𝒕𝒖𝒓𝒆 . 𝑻𝒉𝒂𝒕 𝒊𝒔 𝒆𝒂𝒄𝒉 𝒎𝒆𝒎𝒃𝒆𝒓 𝒊𝒔 𝒂𝒕𝒕𝒂𝒄𝒉𝒆𝒅 𝒕𝒐 𝒊𝒕𝒔 𝒏𝒆𝒊𝒈𝒉𝒃𝒐𝒓𝒊𝒏𝒈 𝒆𝒍𝒆𝒎𝒆𝒏𝒕𝒔. 𝑨𝒏𝒅 𝒘𝒆 𝒄𝒂𝒏 𝒓𝒆𝒑𝒓𝒆𝒔𝒆𝒏𝒕 𝒔𝒕𝒂𝒄𝒌 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒕𝒉𝒓𝒐𝒖𝒈𝒉 𝒂𝒓𝒓𝒂𝒚𝒔.

𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝑻𝒉𝒓𝒐𝒖𝒈𝒉 𝑷𝒓𝒐𝒈𝒓𝒂𝒎

𝑻𝒉𝒆 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒏 𝒊𝒎𝒑𝒍𝒆𝒎𝒆𝒏𝒕𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝒔𝒕𝒂𝒄𝒌 𝒕𝒉𝒓𝒐𝒖𝒈𝒉 𝒑𝒓𝒐𝒈𝒓𝒂𝒎 𝒂𝒔 𝒇𝒐𝒍𝒍𝒐𝒘𝒔:

1. 𝑾𝒆 𝒉𝒂𝒗𝒆 𝒗𝒂𝒓𝒊𝒂𝒃𝒍𝒆𝒔 𝒔𝒖𝒄𝒉 𝒂𝒔 𝒕𝒐𝒑,𝒔𝒊𝒛𝒆 𝒂𝒏𝒅 *𝒔. 𝑻𝒉𝒆 𝒗𝒂𝒓𝒊𝒂𝒃𝒍𝒆 𝒕𝒐𝒑 𝒑𝒐𝒊𝒏𝒕 𝒕𝒐 𝒕𝒐𝒑 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌, 𝒔𝒊𝒛𝒆 𝒊𝒔 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒔𝒊𝒛𝒆 𝒂𝒏𝒅 *𝒔 𝒊𝒔 𝒕𝒐 𝒄𝒓𝒆𝒂𝒕𝒆 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒊𝒏 𝒕𝒉𝒆 𝒉𝒆𝒂𝒑 𝒎𝒆𝒎𝒐𝒓𝒚.

2. 𝑪𝒓𝒆𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌.



𝒔𝒕→𝒔𝒊𝒛𝒆 ,𝒉𝒆𝒓𝒆 𝒘𝒆 𝒕𝒂𝒌𝒆 𝒕𝒉𝒆 𝒔𝒊𝒛𝒆 𝒇𝒓𝒐𝒎 𝒖𝒔𝒆𝒓 𝒕𝒐 𝒄𝒓𝒆𝒂𝒕𝒆 𝒂 𝒅𝒚𝒏𝒂𝒎𝒊𝒄 𝒂𝒓𝒓𝒂𝒚 𝒕𝒐 𝒄𝒓𝒆𝒂𝒕𝒆 𝒂 𝒔𝒕𝒂𝒄𝒌.

𝒔𝒕→𝒕𝒐𝒑= -1 ,𝒂𝒔 𝒕𝒐𝒑= -1 𝒓𝒆𝒑𝒆𝒔𝒆𝒏𝒕𝒔 𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝒆𝒎𝒑𝒕𝒚.

𝒔𝒕→𝒔=(𝒊𝒏𝒕*)𝒎𝒂𝒍𝒍𝒐𝒄 (𝒔𝒕→𝒔𝒊𝒛𝒆*𝒔𝒊𝒛𝒆𝒐𝒇(𝒊𝒏𝒕)) 𝒊𝒔 𝒅𝒐𝒏𝒆 𝒕𝒐 𝒄𝒓𝒆𝒂𝒕𝒆 𝒂𝒓𝒓𝒂𝒚 𝒊𝒏 𝒉𝒆𝒂𝒑 𝒎𝒆𝒎𝒐𝒓𝒚.

𝑨𝒔 𝒘𝒆 𝒂𝒓𝒆 𝒈𝒐𝒊𝒏𝒈 𝒕𝒐 𝒔𝒉𝒐𝒘 𝒔𝒕𝒂𝒄𝒌 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏𝒂𝒍𝒊𝒕𝒚 𝒕𝒉𝒓𝒐𝒖𝒈𝒉 𝒂𝒓𝒓𝒂𝒚.

3. 𝑷𝒖𝒔𝒉 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏



𝒇𝒊𝒓𝒔𝒕 𝒘𝒆 𝒉𝒂𝒗𝒆 𝒕𝒐 𝒄𝒉𝒆𝒄𝒌 𝒕𝒉𝒂𝒕 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝒇𝒖𝒍𝒍 𝒐𝒓 𝒏𝒐𝒕.

𝒊𝒇 𝒕𝒐𝒑==𝒔𝒊𝒛𝒆-1 ,𝒊.𝒆.𝒊𝒇 𝒔𝒊𝒛𝒆 𝒊𝒔 4 𝒕𝒉𝒆𝒏 𝒘𝒆 𝒘𝒊𝒍𝒍 𝒉𝒂𝒗𝒆 𝒂[0],𝒂[1],𝒂[2],𝒂[3] ,𝒉𝒆𝒏𝒄𝒆 𝒔𝒊𝒛𝒆 𝒘𝒊𝒍𝒍 𝒊𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒇𝒓𝒐𝒎 0 𝒕𝒐 3. 𝒕𝒉𝒆𝒏 𝒕𝒐𝒑= -1 ,𝒘𝒉𝒆𝒏 𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝒆𝒎𝒑𝒕𝒚,

1𝒔𝒕 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒑𝒖𝒔𝒉→ 𝒕𝒐𝒑= 𝒕𝒐𝒑+1=0 .

2𝒏𝒅 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒑𝒖𝒔𝒉→ 𝒕𝒐𝒑=𝒕𝒐𝒑+1=1.

3𝒓𝒅 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒑𝒖𝒔𝒉→ 𝒕𝒐𝒑=𝒕𝒐𝒑+1=2.

4𝒓𝒕𝒉 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒑𝒖𝒔𝒉→ 𝒕𝒐𝒑=𝒕𝒐𝒑+1=3.

𝒊𝒇(𝒕𝒐𝒑==𝒔𝒊𝒛𝒆-1) 𝒕𝒉𝒆𝒏 𝑺𝒕𝒂𝒄𝒌 𝒊𝒔 𝑭𝒖𝒍𝒍.

𝒊𝒇 𝒏𝒐𝒕 𝒇𝒖𝒍𝒍 ,𝒕𝒉𝒆𝒏 𝒘𝒆 𝒊𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒕𝒐𝒑=𝒕𝒐𝒑+1. 𝒂𝒏𝒅 𝒑𝒖𝒔𝒉 𝒕𝒉𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒂𝒕 𝒕𝒐𝒑 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌= 𝒔[𝒕𝒐𝒑]=𝒆𝒍𝒆𝒎𝒆𝒏𝒕.

4. 𝑷𝒐𝒑 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏



𝒊𝒇 𝒕𝒐𝒑 = -1 𝒉𝒆𝒏𝒄𝒆 𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝒆𝒎𝒑𝒕𝒚 𝒕𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆 𝑼𝒏𝒅𝒆𝒓𝒇𝒍𝒐𝒘 𝒆𝒍𝒔𝒆 𝒘𝒆 𝒅𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒕𝒉𝒆 𝒕𝒐𝒑 . 𝑨𝒔 𝒘𝒆 𝒅𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒕𝒉𝒆 𝒕𝒐𝒑 𝒂𝒏𝒅 𝒔𝒆𝒕 𝒕𝒐 𝒕𝒉𝒆 𝒂𝒓𝒓𝒂𝒚 𝒔𝒂𝒚, 𝒆𝒂𝒓𝒍𝒊𝒆𝒓 𝒕𝒐𝒑 =3 , 𝒏𝒐𝒘 𝒕𝒐𝒑 𝒊𝒔 𝒅𝒆𝒄𝒓𝒆𝒎𝒆𝒏𝒕𝒆𝒅 𝒕𝒐 2 𝒂𝒏𝒅 𝒘𝒆 𝒓𝒆𝒕𝒖𝒓𝒏 𝒔[2] , 𝒉𝒆𝒏𝒄𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒂𝒕 𝒔[3] 𝒈𝒆𝒕𝒔 𝒑𝒐𝒑𝒑𝒆𝒅 𝒐𝒖𝒕.

5. 𝑷𝒆𝒆𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏

𝑷𝒆𝒆𝒌 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒓𝒆𝒕𝒖𝒓𝒏𝒔 𝒕𝒉𝒆 𝒕𝒐𝒑 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒊.𝒆., 𝒕𝒉𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒘𝒉𝒆𝒓𝒆 𝒕𝒐𝒑 𝒊𝒔 𝒑𝒐𝒊𝒏𝒕𝒆𝒅 𝒂𝒕 𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒔𝒕𝒂𝒕𝒆.

𝑯𝒆𝒓𝒆 𝒘𝒆 𝒉𝒂𝒗𝒆 𝒆𝒙𝒕𝒓𝒂 𝒄𝒉𝒆𝒄𝒌𝒊𝒏𝒈 𝒐𝒇 𝒆𝒎𝒑𝒕𝒊𝒏𝒆𝒔𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌.



𝑵𝒐𝒕𝒆 𝒉𝒆𝒓𝒆 𝒑𝒆𝒆𝒌(𝒔𝒕𝒄𝒌) 𝒂𝒏𝒅 𝒊𝒏𝒕 𝒑𝒆𝒆𝒌 (𝑺𝒕𝒂𝒄𝒌 𝒔𝒕) {…} 𝒊𝒔 𝒄𝒂𝒍𝒍 𝒃𝒚 𝒗𝒂𝒍𝒖𝒆 𝒏𝒐𝒕 𝒄𝒂𝒍𝒍 𝒃𝒚 𝒓𝒆𝒇𝒆𝒓𝒆𝒏𝒄𝒆 𝒘𝒉𝒆𝒓𝒆 𝒔𝒕 𝒊𝒔 𝑭𝒐𝒓𝒎𝒂𝒍 𝑷𝒂𝒓𝒂𝒎𝒆𝒕𝒆𝒓 (𝑭𝒐𝒓𝒎𝒂𝒍 𝑶𝒃𝒋𝒆𝒄𝒕 𝒐𝒇 𝑺𝒕𝒓𝒖𝒄𝒕𝒖𝒓𝒆) 𝒂𝒏𝒅 𝒔𝒕𝒄𝒌 𝒊𝒔 𝑨𝒄𝒕𝒖𝒂𝒍 𝑷𝒂𝒓𝒂𝒎𝒆𝒕𝒆𝒓 (𝑨𝒄𝒕𝒖𝒂𝒍 𝑶𝒃𝒋𝒆𝒄𝒕 𝒐𝒇 𝑺𝒕𝒓𝒖𝒄𝒕𝒖𝒓𝒆).

𝒊𝒇(!𝒊𝒔𝑬𝒎𝒑𝒕𝒚(𝒔𝒕)) 𝒊.𝒆.𝒊𝒔𝑬𝒎𝒑𝒕𝒚 𝒊𝒔 𝒏𝒐𝒕 1 𝒊.𝒆.0 (𝒇𝒂𝒍𝒔𝒆)

𝒐𝒓 𝒊𝒇(𝒊𝒔𝑬𝒎𝒑𝒕𝒚==0) 𝒕𝒉𝒆𝒏 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒓𝒆𝒕𝒖𝒓𝒏 𝒕𝒐𝒑.

𝑬𝒍𝒔𝒆 𝒊𝒔𝑬𝒎𝒑𝒕𝒚(𝒔𝒕) 𝒊𝒔 1 (𝒕𝒓𝒖𝒆)𝒕𝒉𝒆𝒏 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒓𝒆𝒕𝒖𝒓𝒏-1. 𝑨𝒏𝒅 𝒘𝒆 𝒌𝒏𝒐𝒘 ,𝒊𝒇 𝑻𝒐𝒑= -1 ,𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝑬𝒎𝒑𝒕𝒚.

6. 𝑰𝒔 𝑬𝒎𝒑𝒕𝒚 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏



𝒊𝒇 𝒕𝒐𝒑 = -1,𝒕𝒉𝒆𝒏 𝒊𝒕 𝒓𝒆𝒕𝒖𝒓𝒏𝒔 1 (𝒕𝒓𝒖𝒆)𝒆𝒍𝒔𝒆 𝒓𝒆𝒕𝒖𝒓𝒏 0 (𝑭𝒂𝒍𝒔𝒆).

7. 𝑰𝒔 𝑭𝒖𝒍𝒍 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏



𝑵𝒐𝒕𝒆 == 𝒊𝒔 𝒓𝒆𝒍𝒂𝒕𝒊𝒐𝒏𝒂𝒍 𝒐𝒑𝒆𝒓𝒂𝒕𝒐𝒓, 𝒄𝒉𝒆𝒄𝒌𝒔 𝒊𝒇 1𝒔𝒕 𝑶𝒑𝒆𝒓𝒂𝒏𝒅 = 2𝒏𝒅 𝑶𝒑𝒆𝒓𝒂𝒏𝒅 𝒊𝒔 𝒕𝒓𝒖𝒆. 𝒊.𝒆. 𝒕𝒐𝒑 = 𝒔𝒊𝒛𝒆-1 𝒊𝒔 𝒕𝒓𝒖𝒆, 𝒕𝒉𝒆𝒏 𝒊𝒕 𝒓𝒆𝒕𝒖𝒓𝒏𝒔 1 (𝑻𝒓𝒖𝒆).

8. 𝑺𝒕𝒂𝒄𝒌 𝑻𝒓𝒂𝒗𝒆𝒓𝒔𝒂𝒍



𝑯𝒆𝒓𝒆 𝒘𝒆 𝒕𝒓𝒂𝒗𝒆𝒓𝒔𝒆 𝒂𝒏𝒅 𝒈𝒆𝒕 𝒂𝒍𝒍 𝒕𝒉𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 ,𝒕𝒉𝒂𝒕 𝒂𝒓𝒆 𝒃𝒆𝒊𝒏𝒈 𝒑𝒖𝒔𝒉𝒆𝒅 𝒊𝒏𝒕𝒐 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌.

9. 𝑫𝒆𝒍𝒆𝒕𝒊𝒏𝒈 𝒕𝒉𝒆 𝑺𝒕𝒂𝒄𝒌

𝑵𝒐𝒘 , 𝒘𝒉𝒆𝒏 𝒘𝒆 𝒆𝒙𝒊𝒕 𝒇𝒓𝒐𝒎 𝒔𝒕𝒂𝒄𝒌 𝒂𝒔:



𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏 𝒔𝒕𝒐𝒓𝒆𝒅 𝒊𝒏:



𝒉𝒆𝒂𝒅𝒆𝒓 𝒇𝒊𝒍𝒆.



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆 𝒂𝒔 𝒘𝒆 𝒆𝒙𝒊𝒕 𝒇𝒓𝒐𝒎 𝑺𝒕𝒂𝒄𝒌 , 𝒇𝒊𝒓𝒔𝒕 𝒘𝒆 𝒇𝒓𝒆𝒆 𝒔𝒕𝒂𝒄𝒌 , 𝒕𝒉𝒆𝒏 𝒂𝒔𝒔𝒊𝒈𝒏 𝒕𝒉𝒆 𝒑𝒐𝒊𝒏𝒕𝒆𝒓 𝒗𝒂𝒓𝒊𝒂𝒃𝒍𝒆 𝒕𝒐 𝑵𝑼𝑳𝑳 𝒂𝒏𝒅 𝒕𝒉𝒆𝒏 𝒆𝒙𝒊𝒕 𝒂𝒔 𝒉𝒆𝒓𝒆 𝒘𝒆 𝒂𝒓𝒆 𝒋𝒖𝒔𝒕 𝒅𝒆𝒔𝒄𝒓𝒊𝒃𝒊𝒏𝒈 𝒕𝒉𝒆 𝒅𝒚𝒏𝒂𝒎𝒊𝒄 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝒕𝒉𝒆 𝒑𝒓𝒐𝒈𝒓𝒂𝒎.

𝑻𝒉𝒊𝒔 𝒊𝒔 𝒂𝒍𝒍 𝒂𝒃𝒐𝒖𝒕 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝒔𝒕𝒂𝒄𝒌.

𝑪𝒂𝒍𝒄𝒖𝒍𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏

1. 𝑪𝒓𝒆𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌.



𝑯𝒆𝒏𝒄𝒆 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒐𝒇 𝑪𝒓𝒆𝒂𝒕𝒊𝒐𝒏 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌 =𝑶(1)+𝑶(1)+𝑶(1)+𝑶(1)+𝑶(1)+𝑶(1)

=𝑶(1)

2. 𝑷𝒖𝒔𝒉.



𝑯𝒆𝒏𝒄𝒆 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒐𝒇 𝑰𝒏𝒔𝒆𝒓𝒕𝒊𝒐𝒏 = 𝑶(1)+𝑶(1)+𝑶(1)+𝑶(1)+𝑶(1)=𝑶(1)

𝑵𝒐𝒘, 𝑶(1) 𝒊𝒔 𝒇𝒐𝒓 𝒔𝒊𝒏𝒈𝒍𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒘𝒉𝒂𝒕 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒇𝒐𝒓 `𝒏` 𝒕𝒊𝒎𝒆𝒔 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒂𝒔 𝒘𝒆 𝒌𝒏𝒐𝒘 𝒏 𝒕𝒊𝒎𝒆𝒔 1=𝒏 ,𝒉𝒆𝒏𝒄𝒆 𝒊𝒕 𝒎𝒖𝒔𝒕 𝒈𝒆𝒏𝒆𝒓𝒂𝒕𝒆 𝑶(𝒏), 𝒃𝒖𝒕 𝒉𝒆𝒓𝒆 𝒘𝒆 𝒉𝒂𝒗𝒆 𝒂𝒏𝒂𝒍𝒚𝒛𝒆 𝒂𝒄𝒄𝒐𝒓𝒅𝒊𝒏𝒈 𝒕𝒐 𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 .



𝑯𝒆𝒏𝒄𝒆 𝒇𝒐𝒓 𝒂𝒏 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝑷𝒖𝒔𝒉 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒑𝒆𝒓𝒇𝒐𝒓𝒎𝒆𝒅 𝒊𝒏 𝒕𝒉𝒆 𝒕𝒐𝒑 𝒐𝒇 𝒑𝒂𝒓𝒕𝒊𝒄𝒖𝒍𝒂𝒓 𝒔𝒕𝒂𝒄𝒌 𝒘𝒉𝒊𝒄𝒉 𝒈𝒆𝒏𝒆𝒓𝒂𝒕𝒆𝒔 𝑶(1) 𝒕𝒊𝒎𝒆 𝒄𝒐𝒎𝒑𝒆𝒙𝒊𝒕𝒚.

𝑯𝒆𝒏𝒄𝒆,𝑶(1)+𝑶(1)+𝑶(1)+⋯+𝑶(1) 𝒇𝒐𝒓 𝒆𝒂𝒄𝒉 𝑷𝒖𝒔𝒉 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏=𝑶(1).

3. 𝑷𝒐𝒑 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏



𝑯𝒆𝒏𝒄𝒆 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒐𝒇 𝑷𝒐𝒑 = 𝑶(1)+𝑶(1)+𝑶(1)+𝑶(1)=𝑶(1).

𝑵𝒐𝒘, 𝑶(1) 𝒊𝒔 𝒇𝒐𝒓 𝒔𝒊𝒏𝒈𝒍𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒘𝒉𝒂𝒕 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒇𝒐𝒓 `𝒏` 𝒕𝒊𝒎𝒆𝒔 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒂𝒔 𝒘𝒆 𝒌𝒏𝒐𝒘 𝒏 𝒕𝒊𝒎𝒆𝒔 1=𝒏 ,𝒉𝒆𝒏𝒄𝒆 𝒊𝒕 𝒎𝒖𝒔𝒕 𝒈𝒆𝒏𝒆𝒓𝒂𝒕𝒆 𝑶(𝒏), 𝒃𝒖𝒕 𝒉𝒆𝒓𝒆 𝒘𝒆 𝒉𝒂𝒗𝒆 𝒂𝒏𝒂𝒍𝒚𝒛𝒆 𝒂𝒄𝒄𝒐𝒓𝒅𝒊𝒏𝒈 𝒕𝒐 𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 .



𝑯𝒆𝒏𝒄𝒆 𝒇𝒐𝒓 𝒂𝒏 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 ( 𝑭𝒊𝒓𝒔𝒕 𝑬𝒍𝒆𝒎𝒆𝒏𝒕 )𝒈𝒆𝒕𝒔 𝑷𝒐𝒑𝒑𝒆𝒅,𝒉𝒆𝒏𝒄𝒆 𝑷𝒐𝒑 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏 𝒘𝒊𝒍𝒍 𝒈𝒆𝒕𝒔 𝒆𝒙𝒆𝒄𝒖𝒕𝒆𝒅 𝒊𝒏 𝒂 𝒑𝒂𝒓𝒕𝒊𝒄𝒖𝒍𝒂𝒓 𝒔𝒕𝒂𝒄𝒌 𝒘𝒉𝒊𝒄𝒉 𝒈𝒆𝒏𝒆𝒓𝒂𝒕𝒆𝒔 𝑶(1) 𝒕𝒊𝒎𝒆 𝒄𝒐𝒎𝒑𝒆𝒙𝒊𝒕𝒚.

𝑯𝒆𝒏𝒄𝒆,𝑶(1)+𝑶(1)+𝑶(1)+⋯+𝑶(1) 𝒇𝒐𝒓 𝒆𝒂𝒄𝒉 𝑷𝒖𝒔𝒉 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏=𝑶(1).

4. 𝑰𝒔 𝑬𝒎𝒑𝒕𝒚 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏



𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚=𝑶(1)+𝑶(1)+𝑶(1)+𝑶(1)=𝑶(1).

5. 𝑰𝒔 𝑭𝒖𝒍𝒍 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏



𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚=𝑶(1)+𝑶(1)+𝑶(1)=𝑶(1).

6. 𝑻𝒓𝒂𝒗𝒆𝒓𝒔𝒂𝒍 𝑶𝒇 𝑺𝒕𝒂𝒄𝒌



𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚=𝑶(𝒏).

7. 𝑷𝒆𝒆𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏



𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚=𝑶(1)+𝑶(1)+𝑶(1)+𝑶(1)=𝑶(1).

8. 𝑫𝒆𝒍𝒆𝒕𝒊𝒐𝒏 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌



𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚=𝑶(1)+𝑶(1)=𝑶(1).

𝑺𝒖𝒎𝒎𝒊𝒏𝒈 𝑼𝒑 𝑻𝒉𝒆 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒐𝒇 𝑨𝒍𝒍 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔

𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆 𝒘𝒆 𝒄𝒂𝒏 𝒔𝒖𝒎 𝒖𝒑 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒂𝒔:

𝑺𝒕𝒂𝒄𝒌 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝑽𝒔 𝑳𝒐𝒐𝒑 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒚.

𝒊𝒏𝒕 𝒔𝒖𝒎=0;
𝒇𝒐𝒓(𝒊𝒏𝒕 𝒊=0;𝒊<𝒏;𝒊++){
𝒔𝒖𝒎=𝒔𝒖𝒎+𝒊;
}



𝑻𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆 𝒊 𝒂𝒏𝒅 𝒔𝒖𝒎 𝒘𝒊𝒍𝒍 𝒈𝒆𝒕 𝒑𝒐𝒑𝒑𝒆𝒅 𝒐𝒖𝒕.

𝑨𝑫𝑫 𝑺𝒖𝒎,𝒊 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒔𝒆𝒏𝒕 𝒕𝒐 𝑰𝒏𝒔𝒕𝒓𝒖𝒄𝒕𝒊𝒐𝒏 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓.

𝑨𝒍𝒐𝒏𝒈 𝑨𝑫𝑫 𝒊,1 𝒊.𝒆 𝒊=𝒊+1.

𝑨𝒏𝒅 𝒘𝒆 𝒘𝒊𝒍𝒍 𝒈𝒆𝒕 𝑹𝒆𝒔𝒖𝒍𝒕=0 𝒂𝒏𝒅 𝒊=1, 𝒉𝒆𝒏𝒄𝒆 𝒅𝒂𝒕𝒂 𝒓𝒆𝒈𝒊𝒔𝒕𝒆𝒓 𝒘𝒊𝒍𝒍 𝒉𝒂𝒗𝒆 𝒏𝒐𝒘 𝑺𝒖𝒎=0 𝒂𝒏𝒅 𝒊=1.

𝑷𝒖𝒔𝒉 𝒊=1 𝒂𝒏𝒅 𝑺𝒖𝒎=0 𝒊𝒏 𝑴𝒆𝒎𝒐𝒓𝒚 𝑺𝒕𝒂𝒄𝒌 .



𝑯𝒆𝒏𝒄𝒆 𝒕𝒉𝒆 𝒑𝒓𝒐𝒄𝒆𝒔𝒔 𝒘𝒊𝒍𝒍 𝒄𝒐𝒏𝒕𝒊𝒏𝒖𝒆 𝒖𝒑 𝒕𝒐 𝒏 𝒕𝒊𝒎𝒆𝒔 𝒂𝒕 𝒔𝒂𝒎𝒆 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏. 𝑾𝒆 𝒄𝒂𝒏 𝒔𝒕𝒂𝒕𝒆 𝒕𝒉𝒂𝒕 𝒕𝒉𝒆 𝒔𝒕𝒂𝒕𝒆𝒎𝒆𝒏𝒕 𝒐𝒓 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒔𝒖𝒎 = 𝒔𝒖𝒎+𝒊 𝒓𝒖𝒏𝒔 𝒖𝒑 𝒕𝒐 𝒊=𝒏 𝒊.𝒆., 𝒏 𝒕𝒊𝒎𝒆𝒔 .

𝑮𝒆𝒏𝒆𝒓𝒂𝒕𝒊𝒏𝒈 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚∶𝑶(𝒏).

𝑾𝒉𝒆𝒓𝒆 𝒂𝒔 𝒊𝒏 𝑷𝒖𝒔𝒉 𝒂𝒏𝒅 𝑷𝒐𝒑 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏:



𝒊.𝒆.,𝑷𝒖𝒔𝒉 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒊𝒏𝒔𝒆𝒓𝒕𝒆𝒅 𝒂𝒕 𝒆𝒂𝒄𝒉 𝑻𝒐𝒑 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌.

𝒊.𝒆.,𝑨𝒕 𝒆𝒂𝒄𝒉 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 𝒕𝒉𝒆 𝑷𝒖𝒔𝒉 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒑𝒆𝒓𝒇𝒐𝒓𝒎𝒆𝒅 𝒂𝒕 𝑶(1) 𝒄𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚.

𝑨𝒍𝒔𝒐,𝒊𝒇 𝒘𝒆 𝒔𝒆𝒆 𝒕𝒉𝒆𝒓𝒆 𝒊𝒔 𝒍𝒐𝒘𝒆𝒓 𝒃𝒐𝒖𝒏𝒅 (1) 𝒂𝒏𝒅 𝒖𝒑𝒑𝒆𝒓 𝒃𝒐𝒖𝒏𝒅(𝒏 𝒊.𝒆.𝒔𝒊𝒛𝒆 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌=𝒏): 1≤ 𝒇(𝒏)≤𝒏 .

𝑯𝒆𝒓𝒆 𝒊𝒇 𝒘𝒆 𝒅𝒐 𝒂𝒗𝒆𝒓𝒂𝒈𝒆 𝒊𝒇 𝒊𝒕 𝒓𝒖𝒏𝒔 𝒖𝒑 𝒕𝒐 𝒏 𝒕𝒊𝒎𝒆𝒔:



𝒊.𝒆.,𝑷𝒐𝒑 𝒐𝒇 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒅𝒐𝒏𝒆 𝒂𝒕 𝒆𝒂𝒄𝒉 𝑻𝒐𝒑(𝑭𝒊𝒓𝒔𝒕 𝑬𝒍𝒆𝒎𝒆𝒏𝒕)𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌.

𝒊.𝒆.,𝑨𝒕 𝒆𝒂𝒄𝒉 𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 𝒕𝒉𝒆 𝑷𝒐𝒑 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒘𝒊𝒍𝒍 𝒃𝒆 𝒑𝒆𝒓𝒇𝒐𝒓𝒎𝒆𝒅 𝒂𝒕 𝑶(1) 𝒄𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚.

𝑨𝒍𝒔𝒐,𝒊𝒇 𝒘𝒆 𝒔𝒆𝒆 𝒕𝒉𝒆𝒓𝒆 𝒊𝒔 𝒍𝒐𝒘𝒆𝒓 𝒃𝒐𝒖𝒏𝒅 (1) 𝒂𝒏𝒅 𝒖𝒑𝒑𝒆𝒓 𝒃𝒐𝒖𝒏𝒅(𝒏 𝒊.𝒆.𝒔𝒊𝒛𝒆 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌=𝒏):1≤ 𝒇(𝒏)≤𝒏

𝑯𝒆𝒓𝒆 𝒊𝒇 𝒘𝒆 𝒅𝒐 𝒂𝒗𝒆𝒓𝒂𝒈𝒆 𝒊𝒇 𝒊𝒕 𝒓𝒖𝒏𝒔 𝒖𝒑 𝒕𝒐 𝒏 𝒕𝒊𝒎𝒆𝒔:

𝑺𝒕𝒂𝒄𝒌-𝑺𝒑𝒂𝒄𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚

𝑰𝒇 𝑺𝒕𝒂𝒄𝒌 𝒓𝒖𝒏𝒔 𝒇𝒐𝒓 `𝒏` 𝒕𝒊𝒎𝒆𝒔 , 𝒆𝒂𝒄𝒉 𝒕𝒊𝒎𝒆𝒔 𝒔𝒑𝒂𝒄𝒆 𝒄𝒐𝒏𝒔𝒖𝒎𝒆𝒔 𝟏 𝒖𝒏𝒊𝒕 𝒂𝒏𝒅 𝒉𝒆𝒏𝒄𝒆 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒂𝒅𝒅 ∶ 𝟏 𝒖𝒏𝒊𝒕 + 𝟏 𝒖𝒏𝒊𝒕 + ⋯ + 𝒏 𝒕𝒊𝒎𝒆𝒔 = 𝒏 𝒖𝒏𝒊𝒕 𝒐𝒇 𝑺𝒑𝒂𝒄𝒆 𝒊𝒏 𝒎𝒆𝒎𝒐𝒓𝒚.



𝑯𝒆𝒏𝒄𝒆 𝑺𝒑𝒂𝒄𝒆 𝒄𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 (𝒇𝒐𝒓 𝒏 𝒑𝒖𝒔𝒉 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏):𝑶(𝒏).

𝑺𝒕𝒂𝒄𝒌 − 𝑨𝒍𝒕𝒆𝒓𝒏𝒂𝒕𝒊𝒗𝒆 𝑨𝒑𝒑𝒓𝒐𝒂𝒄𝒉

𝑳𝒆𝒕 𝒖𝒔 𝒊𝒎𝒑𝒓𝒐𝒗𝒆 𝒕𝒉𝒆 𝒄𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒃𝒚 𝒖𝒔𝒊𝒏𝒈 𝒕𝒉𝒆 𝒂𝒓𝒓𝒂𝒚 𝒅𝒐𝒖𝒃𝒍𝒊𝒏𝒈 𝒕𝒆𝒄𝒉𝒏𝒊𝒒𝒖𝒆. 𝑰𝒇 𝒕𝒉𝒆 𝒂𝒓𝒓𝒂𝒚 𝒊𝒔 𝒇𝒖𝒍𝒍, 𝒄𝒓𝒆𝒂𝒕𝒆 𝒂 𝒏𝒆𝒘 𝒂𝒓𝒓𝒂𝒚 𝒐𝒇 𝒕𝒘𝒊𝒄𝒆 𝒕𝒉𝒆 𝒔𝒊𝒛𝒆 , 𝒂𝒏𝒅 𝒄𝒐𝒑𝒚 𝒕𝒉𝒆 𝒊𝒕𝒆𝒎𝒔 . 𝑾𝒊𝒕𝒉 𝒕𝒉𝒊𝒔 𝒂𝒑𝒑𝒓𝒐𝒂𝒄𝒉 , 𝒑𝒖𝒔𝒉𝒊𝒏𝒈 `𝒏` 𝒊𝒕𝒆𝒎𝒔 𝒕𝒂𝒌𝒆𝒔 𝒕𝒊𝒎𝒆 𝒑𝒓𝒐𝒑𝒐𝒓𝒕𝒊𝒐𝒏𝒂𝒍 𝒕𝒐 𝒏 (𝒏𝒐𝒕 𝒏^𝟐 ).

𝑭𝒐𝒓 𝒔𝒊𝒎𝒑𝒍𝒊𝒄𝒊𝒕𝒚 ,𝒍𝒆𝒕 𝒖𝒔 𝒂𝒔𝒔𝒖𝒎𝒆 𝒕𝒉𝒂𝒕 𝒊𝒏𝒊𝒕𝒊𝒂𝒍𝒍𝒚 𝒘𝒆 𝒔𝒕𝒂𝒓𝒕𝒆𝒅 𝒘𝒊𝒕𝒉 𝒏 = 𝟏 𝒂𝒏𝒅 𝒎𝒐𝒗𝒆𝒅 𝒖𝒑 𝒕𝒐 𝒏 = 𝟑𝟐 . 𝑻𝒉𝒂𝒕 𝒎𝒆𝒂𝒏𝒔 , 𝒘𝒆 𝒅𝒐 𝒕𝒉𝒆 𝒅𝒐𝒖𝒃𝒍𝒊𝒏𝒈 𝒂𝒕 𝟏, 𝟐, 𝟒, 𝟖, 𝟏𝟔. 𝑻𝒉𝒆 𝒐𝒕𝒉𝒆𝒓 𝒘𝒂𝒚 𝒐𝒇 𝒂𝒏𝒂𝒍𝒚𝒛𝒊𝒏𝒈 𝒕𝒉𝒆 𝒔𝒂𝒎𝒆 𝒂𝒑𝒑𝒓𝒐𝒂𝒄𝒉 𝒊𝒔: 𝒂𝒕 𝒏 = 𝟏 ,𝒊𝒇 𝒘𝒆 𝒘𝒂𝒏𝒕 𝒕𝒐 𝒂𝒅𝒅 (𝒑𝒖𝒔𝒉) 𝒂𝒏 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 , 𝒅𝒐𝒖𝒃𝒍𝒆 𝒕𝒉𝒆 𝒄𝒖𝒓𝒓𝒆𝒏𝒕 𝒔𝒊𝒛𝒆 𝒐𝒇 𝒕𝒉𝒆 𝒂𝒓𝒓𝒂𝒚 𝒂𝒏𝒅 𝒄𝒐𝒑𝒚 𝒂𝒍𝒍 𝒕𝒉𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕𝒔 𝒐𝒇 𝒕𝒉𝒆 𝒐𝒍𝒅 𝒂𝒓𝒓𝒂𝒚 𝒕𝒐 𝒕𝒉𝒆 𝒏𝒆𝒘 𝒂𝒓𝒓𝒂𝒚.

𝑨𝒕 𝒏 = 𝟏 , 𝒘𝒆 𝒅𝒐 𝟏 𝒄𝒐𝒑𝒚 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒂𝒕 𝒏 = 𝟐 , 𝒘𝒆 𝒅𝒐 𝟐 𝒄𝒐𝒑𝒚 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔, 𝒂𝒏𝒅 𝒂𝒕 𝒏 = 𝟒, 𝒘𝒆 𝒅𝒐 𝟒 𝒄𝒐𝒑𝒚 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔 𝒂𝒏𝒅 𝒔𝒐 𝒐𝒏. 𝑩𝒚 𝒕𝒉𝒆 𝒕𝒊𝒎𝒆 𝒘𝒆 𝒓𝒆𝒂𝒄𝒉 𝒏 = 𝟑𝟐, 𝒕𝒉𝒆 𝒕𝒐𝒕𝒂𝒍 𝒏𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒄𝒐𝒑𝒚 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔 𝒊𝒔 𝟏 + 𝟐 + 𝟒 +𝟖 + 𝟏𝟔 = 𝟑𝟏 𝒘𝒉𝒊𝒄𝒉 𝒊𝒔 𝒂𝒑𝒑𝒓𝒐𝒙𝒊𝒎𝒂𝒕𝒆𝒍𝒚 𝒆𝒒𝒖𝒂𝒍 𝒕𝒐 𝟐𝒏 𝒗𝒂𝒍𝒖𝒆(𝟑𝟐).

𝑾𝒆 𝒄𝒂𝒏 𝒔𝒆𝒆 𝒕𝒉𝒂𝒕 𝒕𝒉𝒆 𝒔𝒆𝒓𝒊𝒆𝒔 𝒘𝒆 𝒈𝒆𝒕 𝒊𝒔 ∶ 𝟐^𝟎 + 𝟐^𝟏 + 𝟐^𝟐 + 𝟐^𝟑 + 𝟐^𝟒 = 𝟑𝟏 𝒘𝒉𝒊𝒄𝒉 𝒊𝒔 𝒂𝒑𝒑𝒓𝒐𝒙𝒊𝒎𝒂𝒕𝒆𝒍𝒚 𝒆𝒒𝒖𝒂𝒍 𝒕𝒐 𝟐𝒏 𝒗𝒂𝒍𝒖𝒆(𝟑𝟐). 𝑰𝒇 𝒘𝒆 𝒐𝒃𝒔𝒆𝒓𝒗𝒆 𝒄𝒂𝒓𝒆𝒇𝒖𝒍𝒍𝒚, 𝒘𝒆 𝒂𝒓𝒆 𝒅𝒐𝒊𝒏𝒈 𝒕𝒉𝒆 𝒅𝒐𝒖𝒃𝒍𝒊𝒏𝒈 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 `𝒍𝒐𝒈(𝒏)` 𝒕𝒊𝒎𝒆𝒔. 𝑵𝒐𝒘,𝒍𝒆𝒕 𝒖𝒔 𝒈𝒆𝒏𝒆𝒓𝒂𝒍𝒊𝒛𝒆 𝒕𝒉𝒆 𝒅𝒊𝒔𝒄𝒖𝒔𝒔𝒊𝒐𝒏. 𝑭𝒐𝒓 `𝒏` 𝒑𝒖𝒔𝒉 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔 𝒘𝒆 𝒅𝒐𝒖𝒃𝒍𝒆 𝒕𝒉𝒆 𝒂𝒓𝒓𝒂𝒚 𝒔𝒊𝒛𝒆 `𝒍𝒐𝒈(𝒏)` 𝒕𝒊𝒎𝒆𝒔. 𝑻𝒉𝒂𝒕 𝒎𝒆𝒂𝒏𝒔, 𝒘𝒆 𝒘𝒊𝒍𝒍 𝒉𝒂𝒗𝒆 `𝒍𝒐𝒈𝒏` 𝒕𝒆𝒓𝒎𝒔 𝒊𝒏 𝒕𝒉𝒆 𝒆𝒙𝒑𝒓𝒆𝒔𝒔𝒊𝒐𝒏 𝒃𝒆𝒍𝒐𝒘. 𝑻𝒉𝒆 𝒕𝒐𝒕𝒂𝒍 𝒕𝒊𝒎𝒆 𝑻(𝒏) 𝒐𝒇 𝒂 𝒔𝒆𝒓𝒊𝒆𝒔 𝒐𝒇 𝒏 𝒑𝒖𝒔𝒉 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔 𝒊𝒔 𝒑𝒓𝒐𝒑𝒐𝒓𝒕𝒊𝒐𝒏𝒂𝒍 𝒕𝒐:

$$\begin{equation} \begin{split} 𝟏+𝟐+𝟒+𝟖....+ \dfrac{𝒏}{𝟒} + \dfrac{𝒏}{𝟐} + 𝒏 = 𝒏 + \dfrac{𝒏}{𝟐} + \dfrac{𝒏}{𝟒} +...𝟖+𝟒+𝟐+𝟏 \\\ = 𝑶(𝟐𝒏-𝒏(\dfrac{𝟏}{𝟐})^𝒏 ) = 𝑶(𝟐𝒏) = 𝑶(𝒏) \\ \end{split} \end{equation}$$

𝑻(𝒏) 𝒊𝒔 𝑶(𝒏)𝒂𝒏𝒅 𝒕𝒉𝒆 𝒂𝒎𝒐𝒓𝒕𝒊𝒛𝒆𝒅 𝒕𝒊𝒎𝒆 𝒐𝒇 𝒂 𝒑𝒖𝒔𝒉 𝒐𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒊𝒔 𝑶(𝟏).

𝑫𝒆𝒕𝒂𝒊𝒍𝒆𝒅 𝑫𝒊𝒔𝒄𝒖𝒔𝒔𝒊𝒐𝒏𝒔 𝑯𝒆𝒓𝒆 (𝑺𝒕𝒂𝒄𝒌 − 𝑨𝒍𝒕𝒆𝒓𝒏𝒂𝒕𝒊𝒗𝒆 𝑨𝒑𝒑𝒓𝒐𝒂𝒄𝒉)

𝑺𝒕𝒂𝒄𝒌 − 𝑨𝒍𝒕𝒆𝒓𝒏𝒂𝒕𝒊𝒗𝒆 𝑨𝒑𝒑𝒓𝒐𝒂𝒄𝒉-𝑬𝒙𝒑𝒍𝒂𝒏𝒂𝒕𝒊𝒐𝒏

𝟏.𝑰𝑺𝑭𝑼𝑳𝑳 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏 𝒕𝒐 𝒄𝒉𝒆𝒄𝒌 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝒇𝒖𝒍𝒍 𝒐𝒓 𝒏𝒐𝒕 𝒂𝒔 𝒅𝒊𝒔𝒄𝒖𝒔𝒔𝒆𝒅 𝒃𝒆𝒇𝒐𝒓𝒆:



𝟐.𝑫𝒐𝒖𝒃𝒍𝒆 𝑺𝒕𝒂𝒄𝒌 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏 𝒕𝒐 𝒅𝒐𝒖𝒃𝒍𝒆 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒊𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒊𝒔 𝒇𝒖𝒍𝒍 ∶



𝑵𝒐𝒕𝒆:𝑹𝒆𝑨𝒍𝒍𝒐𝒄 𝒘𝒊𝒍𝒍 𝒓𝒆𝒂𝒍𝒍𝒐𝒄𝒂𝒕𝒆 𝒕𝒉𝒆 𝒎𝒆𝒎𝒐𝒓𝒚 𝒂𝒈𝒂𝒊𝒏 𝒘𝒊𝒕𝒉 𝒂 𝒏𝒆𝒘 𝒔𝒊𝒛𝒆 𝒐𝒇 𝒕𝒉𝒆 𝒂𝒓𝒓𝒂𝒚 𝒄𝒓𝒆𝒂𝒕𝒆𝒅.

𝟑. 𝑰𝒏 𝑷𝒖𝒔𝒉 , 𝒘𝒉𝒆𝒏 𝒕𝒉𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 𝒊𝒔 𝒑𝒖𝒔𝒉𝒆𝒅 𝒊𝒏 𝑺𝒕𝒂𝒄𝒌 𝒕𝒉𝒆𝒏 𝒊𝒕𝒔 𝒄𝒉𝒆𝒄𝒌𝒆𝒅 𝒕𝒉𝒂𝒕 𝒊𝒇 𝒊𝒕𝒔 𝒇𝒖𝒍𝒍 𝒕𝒉𝒆𝒏 𝒅𝒐𝒖𝒃𝒍𝒆 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 , 𝒆𝒍𝒔𝒆 𝒋𝒖𝒔𝒕 𝒊𝒏𝒄𝒓𝒆𝒎𝒆𝒏𝒕 𝒕𝒉𝒆 𝒕𝒐𝒑 𝒂𝒏𝒅 𝒑𝒖𝒔𝒉 𝒕𝒉𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕.



𝑵𝒐𝒘, 𝑪𝒐𝒎𝒊𝒏𝒈 𝒃𝒂𝒄𝒌 𝒕𝒐 𝒆𝒙𝒆𝒄𝒖𝒕𝒊𝒐𝒏:

𝑨𝒕 𝒇𝒊𝒓𝒔𝒕 𝒘𝒆 𝒄𝒓𝒆𝒂𝒕𝒆 𝒐𝒃𝒋𝒆𝒄𝒕 𝒐𝒇 𝑺𝒕𝒂𝒄𝒌 𝒂𝒏𝒅 𝒅𝒆𝒄𝒍𝒂𝒓𝒆 𝒂 𝒗𝒂𝒓𝒊𝒂𝒃𝒍𝒆 𝒕𝒐 𝒅𝒆𝒄𝒊𝒅𝒆 𝒘𝒉𝒂𝒕 𝒔𝒉𝒐𝒖𝒍𝒅 𝒃𝒆 𝒄𝒂𝒑𝒂𝒄𝒊𝒕𝒚 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒊𝒏 𝒎𝒂𝒊𝒏 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏.



𝟒.𝑾𝒆 𝒌𝒏𝒐𝒘 𝒅𝒖𝒓𝒊𝒏𝒈 𝒑𝒖𝒔𝒉 𝒊𝒕 𝒘𝒊𝒍𝒍 𝒕𝒂𝒌𝒆 𝟐𝒏 𝒆𝒍𝒆𝒎𝒆𝒏𝒕𝒔 𝒂𝒔 𝒂𝒔 𝒕𝒉𝒆 𝒔𝒊𝒛𝒆 𝒈𝒆𝒕𝒔 𝒅𝒐𝒖𝒃𝒍𝒆𝒅:



𝟓. 𝑵𝒐𝒘 𝒑𝒐𝒑 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏 𝒎𝒖𝒔𝒕 𝒑𝒐𝒑 𝒕𝒉𝒆 𝒇𝒊𝒓𝒔𝒕 𝒔𝒆𝒕 𝒐𝒇 𝒆𝒍𝒆𝒎𝒆𝒏𝒕𝒔 𝒕𝒉𝒂𝒕 𝒂𝒓𝒆 (𝒊𝒏𝒔𝒆𝒓𝒕𝒆𝒅 𝒃𝒆𝒇𝒐𝒓𝒆 𝒕𝒉𝒆 𝒂𝒓𝒓𝒂𝒚 𝒈𝒐𝒕 𝒅𝒐𝒖𝒃𝒍𝒆𝒅 ) ∶



𝑬𝒍𝒔𝒆 , 𝒆𝒗𝒆𝒓𝒚 𝒐𝒕𝒉𝒆𝒓 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏𝒔 𝒂𝒓𝒆 𝒂𝒍𝒍 𝒔𝒂𝒎𝒆 𝒆𝒂𝒓𝒍𝒊𝒆𝒓 𝒅𝒊𝒔𝒄𝒖𝒔𝒔𝒆𝒅 .

𝑺𝒕𝒂𝒄𝒌 − 𝑨𝒍𝒕𝒆𝒓𝒏𝒂𝒕𝒊𝒗𝒆 𝑨𝒑𝒑𝒓𝒐𝒂𝒄𝒉-𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚

𝟏. 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒐𝒇 𝑷𝒖𝒔𝒉 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏:

𝑨𝒏𝒔: 𝑨𝒔 𝒅𝒊𝒔𝒄𝒖𝒔𝒔𝒆𝒅 𝒆𝒂𝒓𝒍𝒊𝒆𝒓,𝑷𝒖𝒔𝒉 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏 𝒉𝒆𝒓𝒆 𝒕𝒂𝒌𝒆𝒔 𝑻(𝒏) = 𝑶(𝒏), 𝒘𝒉𝒆𝒓𝒆 𝒂𝒎𝒐𝒓𝒕𝒊𝒛𝒆𝒅 𝒕𝒊𝒎𝒆 𝒄𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 = 𝑶(𝟏).

𝟐. 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒐𝒇 𝑷𝒐𝒑 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏: 𝑨𝒏𝒔 ∶ 𝑨𝒔 𝒘𝒆 𝒂𝒓𝒆 𝒑𝒐𝒑𝒊𝒏𝒈 𝒇𝒓𝒐𝒎 𝒆𝒂𝒄𝒉 𝒔𝒕𝒂𝒄𝒌 𝒂𝒕 𝒏 𝒕𝒊𝒎𝒆𝒔, 𝒘𝒆 𝒘𝒊𝒍𝒍 𝒕𝒂𝒌𝒆 𝒕𝒉𝒆 𝒂𝒎𝒐𝒓𝒕𝒊𝒛𝒆𝒅 𝒕𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 = 𝑶(𝟏).

𝑨𝒏𝒅 𝑶𝒕𝒉𝒆𝒓 𝑻𝒊𝒎𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 𝒐𝒇 𝒂𝒍𝒍 𝒕𝒚𝒑𝒆𝒔 𝒐𝒇 𝑶𝒑𝒆𝒓𝒂𝒕𝒊𝒐𝒏𝒔 𝒓𝒆𝒎𝒂𝒊𝒏𝒔 𝒔𝒂𝒎𝒆 𝒕𝒉𝒂𝒕 𝒊𝒔 𝑶(𝟏).

𝑺𝒕𝒂𝒄𝒌 − 𝑨𝒍𝒕𝒆𝒓𝒏𝒂𝒕𝒊𝒗𝒆 𝑨𝒑𝒑𝒓𝒐𝒂𝒄𝒉-𝑺𝒑𝒂𝒄𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚

𝑨𝒔 𝒕𝒉𝒆 𝒔𝒕𝒂𝒄𝒌 𝒕𝒂𝒌𝒆𝒔 `𝒏` 𝒕𝒊𝒎𝒆𝒔 𝒑𝒖𝒔𝒉 𝒕𝒂𝒌𝒆𝒔 𝒏 𝒖𝒏𝒊𝒕𝒔 𝒐𝒇 𝒔𝒑𝒂𝒄𝒆 𝒊𝒏 𝒎𝒆𝒎𝒐𝒓𝒚 , 𝒉𝒆𝒏𝒄𝒆 𝒔𝒑𝒂𝒄𝒆 𝒄𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚 = 𝑻(𝒏) = 𝑶(𝒏).

𝑯𝒆𝒏𝒄𝒆, 𝑾𝒆 𝑺𝒖𝒎 𝑼𝒑 𝑻𝒊𝒎𝒆 𝑨𝒏𝒅 𝑺𝒑𝒂𝒄𝒆 𝑪𝒐𝒎𝒑𝒍𝒆𝒙𝒊𝒕𝒚

👉 𝑪++ - 𝑺𝒕𝒂𝒄𝒌 𝑰𝒎𝒑𝒍𝒆𝒎𝒆𝒏𝒕𝒂𝒕𝒊𝒐𝒏