CareerCup

For finding the median of two sorted arrays we will follow the algorithm given below:

Implementation:

int return_median(int a[], int n, int b[], int m){
	int median, min_index = 0, max_index = n;
	while(min_index <= max_index){
		int i = (min_index + max_index) / 2;
		int j = ((n + m + 1) / 2) - i;
		if(j > 0 && i < n && b[j - 1] > a[i])
			min_index = i + 1;
		else if(i > 0 && j < m && b[j] < a[i - 1])
			max_index = i - 1;
		else{
			if(i == 0)
				median = b[j - 1];
			else if(j == 0)
				median = a[i - 1];
			else
				median = max(a[i - 1], b[j - 1]);
		}
	}
	if((n + m) % 2 == 1)
		return (double)median;
	if(i == n)
		return (median + b[j]) / 2.0;
	if(j == m)
		return (median + a[i]) / 2.0;
	else
		return (median + min(a[i], b[j])) / 2.0;
}

For solving the above algorithm we will need to use the concept of multimap and hashmap we will traverse the array and will keep summing the integers in the array and as soon as we find that the sum exists in the hashmap we will check for the number and then, if found we will print the subarray because the logic is that if there is a number from before in the hashmap then, there exist at least one subarray whose sum = 0.

Implementation:

void findsubarray(int arr[], int n){
	int sum = 0;
	unordered_multimap<int, int> map;
	map.insert(pair<int, int>(0, -1));
	for(int i = 0; i < n; i++){
		sum += arr[i];
		if(map.find(sum) != map.end()){
			auto it = map.find(sum);
			for(it = map.begin(); it != map.end(); it++)
				if(it->first == sum)
					cout<<it->first + 1<<" "<<i;
		}
		map.insert(pair<int, int>(sum, i));
	}
}

The above problem can be solved using the concept of the hashmap, where we will first count the frequency of all the integers and then, we will traverse the hashmap and compare check of the frequency if found greater then n / 2 then output the number.

For finding the median of two sorted arrays we will have to so the binary search on the smaller array and then, we need to handle some of the corner test cases such as when the index of the first array is 0 that is it's left part is empty then the next element of the second array becomes the median and also when the index of the first array comes to be equal to its size than, we will return the sum of median along with the next element of the first array and similarly with the second array.

Implementation:

int findmedian(int a[], int n, int b[], int m){
	int median, min_index = 0, max_index = n;
	while(min_index <= max_index){
		 int i = (min_index + max_index) / 2;
		 int j = ((m + n + 1) / 2) - i;
		 if(i < n && j > 0 && b[j - 1] > a[i])
			min_index = i + 1;
		else if(i > 0 && j < m && b[j] < a[i - 1])
			max_index = i - 1;
		else{
			if(i == 0)
				median = b[j - 1];
			else if(j == 0)
				median = a[i - 1];
			else
				median = max(a[i - 1], b[j - 1]);
		}
	}
	if((n + m) % 2 == 1)
		return (double)median;
	if(i == n)
		return (median + b[j]) / 2.0;
	if(j == m)
		return (median + a[i]) / 2.0;
	else{
		return (median + min(b[j], a[i])) / 2.0;
}

For solving the above algorithm we will need to use the binary search in the sorted and rotated array we will first find the mid using (high + low) / 2 and we will check for the condition that the mid element must be greater then the lower index element and then, if yes we will again check for the element being between the low and the mid index if found then traverse the low to mid - 1 else we will traverse the mid + 1 to high subarray, and the next condition will be the opposite of the first.

Implementation:

int findlement(int arr[], int low, int high, int key){
	if(low > high)
		return -1;
	int mid = (high + low) / 2;
	if(arr[mid] == key)
		return mid;
	if(arr[mid] > arr[low]){
		if(key >= arr[low] && key <= arr[mid])
			return findelement(arr, low , mid - 1, key);
		return findelement(arr, mid + 1, high, key);
	}
	if(arr[mid] >= key && key <= arr[high])
		return findelement(arr, mid + 1, high, key);
	return findelement(arr, low , mid - 1, key);
}

One of the best algorithm to find the kth smallest element in the array is to first use a hashmap to count the frequency of every element in the array and then, we will traverse the hashmap and check for the frequency of the numbers if they are greater than 1 then, we will keep reducing the counter of k (which is the kth element we have to find) and when the value of k will be 0 we will print the index which will be our kth smallest element, this is for all distinct element.

One of the best solutions to the above problem is to use the binary search in the array we will check for each of the array elements in the sorted array and we will check if the index at which the element is present must be equal to the array element of the sorted array (sorted in increasing order)

One of the best algorithms to solve the above problem statement is to use the concept of bit manipulation, we will first xor all the numbers from 1 to n - 1 and we will then xor all the array elements and store them in a separate variable and at the end, we will xor both of them together and finally we will get the duplicate element in the array.

Implementation:

int findrepeating(int arr[], int n){
	int xor_numbers = 1;
	int xor_array = arr[0];
	for(int i = 2; i <= n - 1; i++)
		xor_numbers = xor_numbers ^ i;
	for(int i = 1; i < n; i++)
		xor_array = xor_array ^ arr[i];
	return xor_numbers ^ xor_array;
}

The most efficient algorithm to find the missing number in the array is to use the concept of xor we will xor all the array elements and store them in one variable and we will xor all the numbers from 1 to n and store them in one variable and then next we will xor both of them which will return our missing element.

The best approach to solve the above algorithm is to xor all the array elements by themselves and then the element which is repeated the odd number of times will be the final output.

The most efficient algorithm to solve the above problem statement will be to use a hash map we will store the count of every element in the array and then, after all, elements count are stored we will traverse the map and print the element whose count in the array is 1.

One of the most efficient algorithm to find out the intersection of two sorted arrays is to check for the following conditions which are as follows:
1. We will first check for the condition that if the element of the first array is greater than the element of the second array then, we will increment the index of the second array and the other condition will be just the opposite.
2. And the last condition will be that when the data of both are equal then we will increment the index of both the arrays.

Implementation:

void findintersection(int arr_1[], int m, int arr_2[], int n){
	int i = 0;
	int j = 0;
	while(i < m && j < n){
		if(arr_1[i] > arr_2[j])
			j++;
	        if(arr_1[i] < arr_2[j])
			i++;
		if(arr_1[i] == arr_2[j]){
			cout<<arr_1[i]<<" ";
			i++;
			j++;
		}
	}
}

The most efficient way to sort the array of 0s and 1s is to count the total number of 0s present in the array and to count the total number of 1s in the array and then traversing the array from 0 indexes to the count index insert 0 in the array and then next index to the end index insert 1 in the array and hence the array is sorted.

Implementation:

void sort-array(int arr[], int n){
	int count = 0;
	for(int i = 0; i < n; i++)
		if(arr[i] == 1)
			count++;
	for(int i = 0; i < temp; i++){
		arr[i] = 0;
	for(int i = temp; i < (n - temp); i++)
		arr[i] = 1;
}

For solving the above algorithm we will need to do a merge sort operation, and we will compare the elements of the two arrays if the first element of the first array is less than the first element of the second array then increment the index of the first array because there may the next element which intersects with the first array and similarly increment the index of the second array when the element of the second array is less than the first array and when both the array elements are equal then print the element and increment both the array indexes.

There is no need to maintain a counter variable for it, like if you put all the elements of the first array in the hashset and then, keep checking the elements from the hashset which matches and print them while inserting the elements of the first array into the hashset don't check whether the element is present in the array because it will not print the duplicate element.

One of the best algorithms for finding the intersection of two arrays when the arrays are sorted is applying binary search to find all the elements of the other array in the first array and print the elements which are common in both the arrays:

Imlemenatation:

bool binary-search(int arr[], int low, int high, int key){
	if(high >= low){
		int mid = low + (high - low) / 2;
		if(arr[mid] == key)
			return true;
		if(key > arr[mid])
			return binary-search(arr, mid + 1, high, key);
		else
			return binary-search(arr, low, mid - 1, key);
	}
	return false;
}
int main{
	for(int i = 0; i < m; i++){
		if(binary-search(arr_1, 0, n, arr_2[i]) == true)
			cout<<arr_2[i]<<" ";
	}

Time complexity will be O(logn).
Space complexity will be O(1).

And while the array is not sorted then we can use a hashset to find the common elements.

For solving the above algorithm we will use the unique method to place all the array elements in the array itself without using extra space, we will follow the step of the algorithm:
1. Put the pointer to the second last element of the first array and one pointer to the second last of the second array, then we will compare both the data if the element at first array is greater then the element of second array then, shift the array element of the first array to the index just after the element, before that store the next index element in a variable.
2. Now, we will check for the index and the condition for the element of the first array element being larger than the second array element.
3. Keep shifting all the other elements in the same way.

Implementation:

void mergesort(int arr_1[], int arr_2[], int m, int n){
	for(int i = n - 1; i >= 0; i--){
		int j;
		int last = arr_1[m - 1];
		for(j = m - 2; j >= 0 && arr_1[j] > arr_2[i]; j--)
			arr_1[j + 1] = arr_1[j];
		if(j >= 0 || last > arr_2[i]){
			arr_1[j + 1] = arr_2[i];
			arr_2[i] = last;
		}
	}
}

The above algorithm can be solved using the xor concept of bit manipulation and we need to xor all the numbers from 1 to n and then we have to xor all the elements of the array as well and finally we will xor both of them together to get the element which is replaced in the array and so we will get the most optimized algorithm for the same with no extra space and time complexity of O(n).

Implementation:

int findmissing(int arr[], int n){
    int array_xor = arr[0];
    int number_xor = 1;
    for(int i = 2; i <= n + 1; i++)
        number_xor = number_xor ^ i;
    for(int i = 1; i < n; i++)
        array_xor = array_xor ^ arr[i];
    return number_xor ^ array_xor;
}

For finding an element in a rotated and rotated array we need to use the modified binary search which is a little bit different from the normal binary search algorithm which is discussed below:

Implementation:

bool binary-search(int arr[], int low, int high, int key){
	if(high < low)
		return false;
	int mid = (high + low) /2;
	if(arr[mid] == key)
		return true;
	if(arr[low] <= arr[mid]){
		if(key >= arr[low] && arr[mid] >= key)
			return binary-search(arr, low, mid - 1; key);
		return binary-search(arr, mid + 1, high, key);
	}
	if(arr[mid] <= key && high >= key)
		return binary-search(arr, mid + 1, high, key);
	return binary-search(arr, low, mid - 1, key);
}

One of the approaches to solving the above algorithm is using the binary search in a sorted array, we will first take the array elements from the first array and then search it in the second array using binary search and will make sure that the second array is sorted.

Implementation:

int binarysearch(int arr_2[], int low, int high, int key){
	if(high >= low){
		int mid = low + (high - low) / 2;
		if(arr_2[mid] == key)
			return 1;
		else if(arr_2[mid] < key)
			return binarysearch(arr_2, mid + 1, high, key);
		else
			return binarysearch(arr_2, low, mid - 1, key);
	}
	return -1;
}
int main(){
	int m, n;
	int arr_1[m];
	int arr_2[n];
	for(int i = 0; i < m; i++)
		cin>>arr_1[i];
	for(int i = 0; i < n; i++)
		cin>>arr_2[i];
	sort(arr_2, arr_2 + n);
	for(int i = 0; i < m; i++){
		if(binarysearch(arr_2, 0, n - 1, arr_1[i]) == 1)
			count++;
	}
	cout<<count<<endl;
	return 0;
}

Also we can do it using a data structure named hashset or unordered_set and insert the array elements of the first array and then, check for the common elements in the second array using elements stored in the hashset.

For checking palindrome of a string we need to traverse the mid of the string and keep checking that the first and the last characters of the string should not be unequal if they are then, return false else at the end of the string we will return true.

Implementation:

bool findpalindrome(string str){
	int i = 0;
	int j = str.length() - 1;
	while(i != j || i < j)
		if(str[i] != str[j])
			return false;
		i++;
		j--;
	}
	return true;
}

The very easy algorithm for rotation of the matrix by 90 degrees we will be following the algorithm given below:

1. We will first find the transpose of the matrix.
2. We will then reverse the columns or swap them and we will finally get the rotated matrix.

Implementation:

void transpose(int mat[R][C], int R, int C){
	for(int i = 0; i < R; i++){
		for(int j = i; j < C; j++){
			swap(mat[i][j], mat[j][i];
		}
	}
}
void swapp(int mat[R][C], int R, int C){
	for(int i = 0; i < C; i++){
		for(int j = 0, k = R - 1; j < k; i++, k--){
			swap(mat[j][i], mt[k][i]);
		}
	}

The very efficient way to find the missing integer from the array we will first xor all the numbers from 1 to n, then we will xor all the array element numbers and then at the end we will xor the both of them to get the missing number in the array.

Implementation:

int findmissing(int arr[], int n){
	int xor_number = 1;
	int xor_array = arr[0];
	for(int i = 2; i <= n + 1; i++)
		xor_number = xor_number ^ i;
	for(int i = 1; i < n; i++)
		xor_array = xor_array ^ arr[i];
	return xor_array ^ xor_number;
}

For finding the intersection of the two arrays we will need the concept of hashing and at first, we will insert the array elements of the largest array and then, we will check the elements which are present in the hashset if yes then, they are the array elements which are common to both the arrays.

One of the best approach using time O(n) and space O(n) can be done using hashing, we will keep inserting the array elements in the hash table and check that if the element is present in the hash table from before then it is a repeating element in the array and the element will be the final output

Implementation:

int findelement(int arr[], int n){
	unordered_set<int> s;
	for(int i = 0; i < n; i++){
		if(s.find(arr[i]) != s.end())
			return arr[i];
		s.insert(arr[i]);
	}
}

For solving the above algorithm we will need to use the concept of xor we will xor all the array elements and also xor all the numbers from 1 to n and finally xor both the xor of arrays and numbers together.

Implementation:

int findmissing(int arr[], int n){
int xor_number = 1;
int xor_array = arr[0];
for(int i = 2; i <= n + 1; i++)
	xor_number = xor_number ^ i;
for(int i = 1; i < n; i++)
	xor_array = xor_array ^ arr[i];
return xor_array ^ xor_number;

For solving the above algorithm we have to find the element with ocurrance 1 for this we have to add the last bit of every integer in the array and then, we will check if the & operation with the last bit of the integer is 1 then we will increment the sum and then at every step we will check if the sum of all integers is not divisible with 3 if yes then that number will be non repeating in the array.

Implementation:

{int findnonrepeating(int n){
int sum;
int result = 0;
for(int i = 0; i < 32; i++){
	sum = 0;
	int x = (1<<i);
	for(int j = 0; j <n; j++){
		if(arr[j]&x)
			sum++;
	}
	if(sum%3)
		result = result | x;
}
return result;

The number of 1s in the given number can be found by right shifting the binary number of the given integer and counting the number of 1s if it satisfies the condition that (n&1 == 1) else it is not a set bit.

Implementation:

{int findone(int n){
int count = 0;
while(n>0){
if(n&1 == 1)
count++;
n = n << 1;
}
return count;

}

The simple code for swapping the two bits of a given integer will be to iterate to the given two bits and store them in a variable as (x>>i) & 1 and the other as (x>>j) & 1 now, we will xor the two bits and store in a variable as x = (b1 ^ b2) and the, we will put back the bits in their place as x = (x<<i) | (x<<j) and at the end return the xor of the number and x to swap the two bits finally

Implementation:

int swapp(unsgned int n, unsigned i, unsigned int j){
unsigned int p1 = (n<<i) & 1;
unsigned int p2 = (n<<j) & 1;
unsigned int x = (p1^p2);
x = (n<<p1) | (n<<p2);
return n^x;

}

For solving the above algorithm we need to shift the given binary representation of the number 8 to the right and then while we reach on the 9th bit we will check for the condition that if(n&1 == 1) then return true else return false.

For checking that the given number is a power of two or not use the algorithm given below:

Implementation:

bool findpower(int n){
	return n && (!(n&(n-1)));

}

The above algorithm can be solved using hashing, keep calculating the difference of the given number to each element in the array if the element is present in the array then, return true else insert the element into the hashset and when it is not true then, at the end of the operation return false.

Implemenatation:

#include<bits/stdc++.h>
using namespace std;
bool findsum(int arr[], int n, int x){
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        int diff = x - arr[i];
        if(s.find(diff) != s.end())
            return true;
        s.insert(arr[i]);
    }
    return false;
}
int main(){
    int t, n, x;
    cin>>t;
    while(t--){
        cin>>n>>x;
        int arr[n];
        for(int i = 0; i < n; i++)
            cin>>arr[i];
        if(findsum(arr, n, x) == 1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
	//cout<<"Keep learning Keep growing"<<endl;
	return 0;

}

Better time complexity can be achieved by using a hashtable

The most efficient solution of the above algorithm is using the hashset.
The algorithm will be as follows:-
1. Insert all the elements of array 1 in the hashset.
2. Next keep checking the array elements in the hashset of the second array if, the element of the second array is found in the hashset then, the current element is the intersection point of both the arrays.

Implemenatation:

#include<bits/stdc++.h>
using namespace std;
int findintersection(int arr_1[], int arr_2[], int m, int n){
    unordered_set<int> s;
    int count = 0;
    if(m >= n){
       for(int i = 0; i < m; i++){
            if(s.find(arr_1[i]) == s.end())
                s.insert(arr_1[i]);
        } 
        for(int i = 0; i < n; i++){
            if(s.find(arr_2[i]) != s.end()){
                count++;
                s.erase(arr_2[i]);
            }
        }
    }
    else{
        for(int i = 0; i < n; i++){
            if(s.find(arr_2[i]) == s.end())
                s.insert(arr_2[i]);
        }
        for(int i = 0; i < m; i++){
            if(s.find(arr_1[i]) != s.end()){
                count++;
                s.erase(arr_1[i]);
            }
        }
    }
    return count;
    
}
int main(){
    int t, n, m;
    cin>>t;
    while(t--){
        cin>>m>>n;
        int arr_1[m], arr_2[n];
        for(int i = 0; i < m; i++)
            cin>>arr_1[i];
        for(int i = 0; i < n; i++)
            cin>>arr_2[i];
        cout<<findintersection(arr_1, arr_2, m, n)<<endl;
    }
	//cout<<"Keep learning Keep growing"<<endl;
	return 0;

}

Using the xor technique we will get the missing number, find the xor of numbers 1 to 1 million and then find the xor of all array elements and then, finally find the xor both the previously xor elements.

For solving the above algorithm we need to first take the xor of all the numbers from 1 to 100 and then take the xor of all the array elements and then at the end collectively take the xor of both the numbers.

Implementation:

#include<bits/stdc++.h>
using namespace std;
int findmissing(int arr[]){
    int array_xor = arr[0];
    int number_xor = 1;
    for(int i = 2; i <= 100; i++)
        number_xor = number_xor ^ i;
    for(int i = 1; i < 100; i++)
        array_xor = array_xor ^ arr[i];
    return number_xor ^ array_xor;
}
int main(){
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 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, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100};
    cout<<findmissing(arr)<<endl;
    return 0;

}

For calculating the number of zeroes in the given integer we will have to check for n&1 == 0 every time after shifting the bit to the right by 1 and then, if found increment the count and hence, return the count when all the bits have been traversed.

Implementation:

#include<bits/stdc++.h>
using namespace std;
int countno(int r){
    //int r = ~n;
    int count = 0;
    while(r > 0){
        if((r&1) == 0)
            count++;
        r = r>>1;
    }
    return count;
}
int main(){

    int n;
    n = 2;
    cout<<countno(n)<<endl;
    return 0;

}

For solving the above algorithm we can go for level order traversal using a queue, like push the nodes into the queue and during popping it out print the value of the node and just check for the left and the right child of the current node if it exists then, push the nodes into the queue else, skip it. Keep repeating the process till the queue becomes empty.

Implementation:

void levelorder(struct node *root){
if(root == NULL)
return;
queue<struct node *> q;
q.push(root);
while(!q.empty()){
struct node *temp = q.front();
cout<<temp->data<<" ";
q.pop();
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}

}

The algorithm to solve the above problem is to keep doing the check of `if(n&1 == 1)` is this is true increment the counter variable till the number is greater than 0 and at last return the counter variable to get the total number of 1s in the binary representation:

Implementation:

int countbits(int n){
    int count = 0;
    while(n > 0){
        if(n&1 == 1)
            count++;
        n = n>>1;
    }
    return count;
}
using namespace std;
int main(){
    int t, n;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<countbits(n)<<endl;
    }
	return 0;

}

The above algorithms can be solved by following that on every right shift of the binary number it's & operation with 1 should not be 0 if 0 then return true else till the number is greater than 0 return true if not found
Implementation:

#include<bits/stdc++.h>
using namespace std;
int findsetbits(int n){
    while(n > 0){
        if(n&1 == 0)
            return 0;
        n = n>>1;
    }
    return 1;
}
int main(){
    int t, n;
    cin>>t;
    while(t--){
        cin>>n;
        if(findsetbits(n) == 0)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
	return 0;

}

The recursive solution for the above problem will be as given below:
Implementation:

int find_height(struct node *root){
if(root == NULL)
return;
int ldepth = find_height(root->left);
int rdepth = find_height(root->right);
if(ldepth > rdepth)
return ldepth + 1;
return rdepth + 1;

Now, the iterative solution of the above problem will be done by using a queue and doing a level order traversal which is shown below:
Implementation:

int find_height(struct node *root){
if(root == NULL)
return;
queue<struct node*> q;
int height = 0;
q.push(root);
while(1){
int countnodes = q.size();
if(countnodes == 0)
return height;
height++;
if(countnodes > 0){
struct node *node = q.front();
q.pop();
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
countnodes--;
}
}

}

For rotation of the bits we have to rotate the bits by 32 so, we will follow the code given below
Implementation:

return (n << a) | (n >> (32 - a)); or
return (n >> a) | (n << (32 - a));

The most simple algorithm for the above problem is to follow the steps below:
1. First, we will take the xor of the two numbers such that the first number remains in the first variable itself.
2. We will then, take xor of the two numbers again which will put the first number in the second variable also, and then finally take xor so that the second number comes to the first variable
Implementation:

a = a^b;
b = a^b;
a = a^b;

One of the most efficient method to check whether a given number is a power of two or not we will check for the & of the number and the number before itself and then for fulfilling the condition of 0 we have to check for && operation.

Implementation:

#include<bits/stdc++.h>
using namepace std;
bool returnpower(int n){
return n && (!(n & (n - 1)))

}

One of the easy approaches of the above algorithm is to check when the & operation of the given number with 1 is 1 because at that case only 1 bit will be the number where this condition is satisfied and elsewhere it will be 0 so, at the former case increment the counter variable and at the end return the count

Implementation:

#include<bits/stdc++.h>
using namespace std;
int countbits(int n){
int count = 0;
if(n == 0)
return 0;
while(n){
if(n&1 == 1)
count++;
n = n>>1;
}
return count;

}

One of the very basic implementations of the above algorithm is to use the & operator to & it with the number 1 to check if the current bit is 1 or not if yes then increment the count variable else skip the bit and then right shift the bit.

Implementation:

#include<bits/stdc++.h>
using namespace std;
void countbits(int x){
int count = 0;
while(x){
if(x & 1 == 1)
count++;
x = x >> 1;
}
return count;

}

To check if the given number is a power of 2 we have to go through the given below algorithm, i.e. we have to first that the & operator with the previous number's ! operation will either return 1 or 0 and then the && comparison operator will return true or false deciding the number is a power of 2 or not.

Implementation:

#include<bits/stdc++.h>
using namspace std;
bool findresult(int n){
return n && (!(n & (n - 1));
}

One of the best approaches to solving the above algorithm is to use the bit manipulation technique and count the bit 1 in the binary representation

Implementation:

#include<bits/stdc++.h>
using namespace std;
int findcount(int n){
    int count = 0;
    while(n){
        if(n & 1 == 1)
            count++;
        n = n>>1;
    }
    return count;
}
int main()
 {
	int t, n;
	cin>>t;
	while(t--){
	    cin>>n;
	    cout<<findcount(n)<<endl;
	}
	return 0;
}

The most effective algorithm to check for the number is a power of 2 or not we will follow the below implementation:

Implementation:

return x && (!(x&(x - 1)));

which will return either false for the number is not a power of 2 or will return true if it is.

One of the best implementations of the above algorithm is that if we do a & operator with the digit 1 and then if the result comes to be 1 which means that the variable temp contains a bit which is 1 and then, we can increment the counter variable and then we can shift the number to right side and then again check till the number is not equal to zero.

Implementation:

#include<bits/stdc++.h>
using namespace std;
int findbits(int num){
  int count = 0; 
  int temp = num; 
  while(temp != 0){ 
    if((temp & 1) == 1){ 
        count++; 
        temp = temp>>1; 
    } 
  }
  return count;
}
int main(){
    cout<<findbits(3)<<endl;

}