PROBLEM LINK: Practice
Author: Manzood Naqvi
Editorialist: Manzood Naqvi
DIFFICULTY:
EASY
SOLUTION:
For this problem, it will suffice to traverse through the array and check if each element is a power of two by the following:
- While the number is divisible by 2, keep dividing it by 2.
If the resultant number is greater than 1, then it is not a power of 2, and we’ve found our answer.
If we haven’t found any such number, then we print -1.
Time Complexity: O(N*log(N))
CODE:
#include "bits/stdc++.h"
using namespace std;
int32_t main () {
int t;
cin >> t;
while (t--) {
int n;
scanf("%d", &n);
vector <int> id_numbers(n);
int answer = -1;
for (int i = 0; i < n; i++) {
scanf("%d", &id_numbers[i]);
while (id_numbers[i] % 2 == 0) {
id_numbers[i] /= 2;
}
if (id_numbers[i] > 1) {
answer = i;
}
}
printf("%d\n", answer);
}
}