O(n), where n is the number of bits in the larger of the two numbers. This is because, in each iteration, at least one higher-order bit of b becomes 0. In the worst-case scenario, it takes O(n) iterations to reduce b to 0.

🧺 Space complexity: O(1), since no additional space is required apart from a constant number of variables (a, b, carry) used during the computation.

Method 2 - Recursive Half Adder

Same approach, but recursive

Code

[{"language":"Java","code":"class Solution {\n    public int getSum(int a, int b) {\n        if (b == 0) {\n            return a; // Base case: no carry left\n        }\n        return getSum(a ^ b, (a & b) << 1); // Recursive step\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><s

Related Tags