Количество пар с постоянной разницей и побитовым И ноль

Question

Как найти количество пар, разность которых равна заданной константе, а их побитовое И равно нулю?В основном все (x, y) такие, что xy = k;где k - заданная константа, а x & y = 0;

Answer 1

Интересная проблема.

Пусть k _n-1 ... k ₁ k ₀ beдвоичное представление k .

Пусть l будет индексом наименьшего i такого, что k _i = 1
Мы можемотметим, что потенциальная пара решений x и y должна иметь все свои биты i , i

Answer 2

Реализация Java была бы такой ...

import java.util.ArrayList;

public class FindPairs {

    public static void main(String args[]) {
        int arr[] = {1,3,4,5,6,9};
        int k = 3;
        ArrayList<String> out = new ArrayList<String>();

        for(int i=0; i<arr.length; i++) {
            for(int j=i+1; j<arr.length; j++) {
                if((Math.abs(arr[i]-arr[j]) == k) && ((arr[i]&arr[j]) == 0)) {
                    out.add("("+arr[i]+","+arr[j]+")");
                }
            }
        }
        if(out.size()>0) {
            for(String pair:out) {
                System.out.println(pair);
            }
        }else {
            System.out.println("No such pair !");
        }   
    }
}