降低以下程序的时间复杂度

Question

import java.util.Scanner;
class Special_Pairs{

private static Scanner scan;


public static void main(String [] args) {
    byte t;
    int n;
    scan = new Scanner(System.in);
    t=scan.nextByte();
    int[] a=new int[100000];
    while(t>0)
    {
        int i,j,count=0;
        n=scan.nextInt();
    for(i=0;i<n;i++)
    {
        a[i]=scan.nextInt();
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(((a[i]&a[j])==0)||((a[j]&a[i])==0))
            {
                count++;
            }
        }
    }
    t--;
    System.out.println(count);
    }       
}
}

帮我降低这个程序的时间复杂度

问题：

你得到了一个大小为 N 的整数数组 A。你必须报告有序对的数量 (i,j)，使得 A[i] & A[j]=0。这里&表示BITWISE AND，(i,j)和(j,i)被认为是不同的。

输入： 第一行包含测试用例的 T 数。每个测试的第一行包含 N。下一行包含 N 个整数 - 第 i 个整数 A[i].

输出：输出每个测试用例的此类对数。

约束条件：T≤10； N≤100000； A[i] ≤ 1000000

示例输入（明文Link）

1 5 41 47 34 40 29

样本输出（明文Link）

2

解释：这些是必需的对(3 5) (5 3)

Answer 1

如果您正在参加编程比赛（如 ICPC 或类似的比赛），也许您不应该使用 Scanner。从键盘读取太慢了。我已经参加过 ICPC，但我曾经使用 C++。也许你应该尝试 BufferedReader 而不是 Scanner。

Answer 2

我建议为此进行三项优化。我也修改了代码。

外循环的每次迭代不必总是从0开始。第二个循环可以从第一个循环的current+1开始。所以不会比较你已经比较过的元素。
您不需要同时检查 (i,j) 和 (j,i)。如果一个为零，则另一个将始终为零。
您无需初始化固定大小的数组。你总是可以初始化它读取 n.

import java.util.Scanner;

public class Pairs {
  public static void main(String [] args) {
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    while(t > 0) {
      t--;
      int count = 0;
      int n = scan.nextInt();
      int a[] = new int[n];
      for(int i = 0; i<n; i++) {
        a[i]=scan.nextInt();
      }
      for(int i = 0; i<n-1; i++) {
        for(int j = i+1; j<n; j++) {
          if((a[i] & a[j])==0)
          {
            count += 2;
          }
        }
      }
      System.out.println(count);
    }
  }
}

降低以下程序的时间复杂度

Reduce Time complexity of the following program

time

reduce

time-complexity

问题：