Find Missing Number

Complexity o(n)
Input : arr[] = {2,4,1,5,6};
Output : 3
Code :
int arr[]={2,4,1,5,6};
int findMissingNumber(){
    int arrSize = sizeof(arr)/sizeof(int);
    int num = arr[0];
    int num2 = 1;
    int i;
    for( i= 1;i
            num ^=arr[i]; // xor all element of array
            num2 ^= (i+1); // xor all indexes of array from 2 to n+1
        }
    num2 ^= (i+1);
    int res = num^num2; // xor two results will give us the missing number from array
    return res;
    }

DS and Algorithms

How to find the power of a number with log(n) complexity?
Problem : Compute a^n where n belongs to N
Native approach : multiple the base exponent times. Complexity will be O(n).
How can we improve this.
Divide and Conquer method can be used.
a^n =
a^n/2 * a^n/2 if n is even;
a^(n–1)/2 * a^(n–1)/2 ⋅ a if n is odd.
T(n) = T(n/2) + Θ(1) ⇒ T(n) = O(lg n).

C++ Implementation :

double power(int base,int exp){
    if(exp == 0 ){
            return 1;
        }
    if(base == 0){
            return 0;
        }
    if(exp == 1){
            return base;
        }
    if(exp %2 == 0){
            return power(base,exp/2)* power(base,exp/2);
        }
    else{
            return (power(base,(exp-1)/2)*power(base,(exp-1)/2)*base);
        }
    }
Limitations : Negative exponent and base cases are not handled.