Table of Contents

ExplanationImplementation

Official Analysis

Explanation

Hint 1

Hint 2

Hint 3

Solution

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <bits/stdc++.h>
using namespace std;
const int MAX_BIT = 20;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) { cin >> a[i]; }

Java

import java.io.*;
import java.util.*;
public class AndOrSquareSum {
public final static int MAX_BIT = 20;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());

Python

MAX_BIT = 20
n = int(input())
a = list(map(int, input().split()))
# Count the number of active bits at each position.
num_bits = [0] * MAX_BIT
for i in range(MAX_BIT):
for j in range(n):
if a[j] & (1 << i):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!