Codeforces Round 828 (Div. 3) 1744D. Divisibility by 2^n Solution

 

Problem Link :  https://codeforces.com/problemset/problem/1744/D

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. int32_t main() {
5. ios_base::sync_with_stdio(0);
6. cin.tie(0);
7. int t;
8. cin >> t;
9. while (t--) {
10. int n ; cin >> n ;
11. int cnt = 0 ;
12. std::vector<int> v;
13. for ( int i = 1 ; i <= n ; i++){
14. int x ;
15. cin >> x ;
16. while (x % 2 == 0){
17. x /= 2;
18. cnt++ ;
19. }
20.  
21. int cur = i ;
22. int temp = 0 ;
23. while (cur % 2 == 0) {
24. cur /= 2;
25. temp++ ;
26. }
27. v.push_back(temp) ;
28. }
29. if (cnt >= n ){
30. cout <<0<<"\n";
31. }
32. else {
33. int ans = 0 ;
34. sort(v.rbegin(),v.rend()) ;
35. for ( auto i : v) {
36. cnt += i ;
37. ans++ ;
38. if (cnt >= n){
39. cout << ans <<"\n" ;
40. break ;
41. }
42. }
43. if ( cnt < n )
44. cout <<"-1\n";
45. }
46. }
47. return 0 ;
48. }