CODBLND1 - Editorial

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);
    }
}