Алгоритм поиска одного числа XOR

Question

public class UniqueNumber {
public static void main(String[] args) throws IOException {
    File file = new File("input.txt");
    Scanner scanner = new Scanner(file);
    while(scanner.hasNextLine()) {
        Integer line = scanner.nextInt();
        //System.out.println(line);
        int a [] = new int[line];
        int ans = a[0];
        for (int lineIndex = 1; lineIndex < a.length; lineIndex++) {
            ans ^= a[lineIndex];
        }
        System.out.println(ans);
    }

}

} Необходимо сделать поиск одного числа без пары среди все чисел у которых есть пары Почему-то алгоритм перебора не работает .... XOR ?? Надо узнать число из файла в вертикальном порядке, а в выводе число, у которого нет одинаковых пары

Answer 1

тут простая булева алгебра

пример

1 XOR 1 = 0 
0 XOR 0 = 0

0 XOR 1 = 1 
1 XOR 0 = 1

отсюда если мы имеем массив 1,1,2,2,3,3,4,4,5,5,6,6,7

повторяются все за исключением 7

1 XOR 1 XOR 2 XOR 2 XOR 3 XOR 3 XOR 4 XOR 4 XOR 5 XOR 5 XOR 6 XOR 6 XOR 7 или

0001 XOR 0001 XOR 0010 XOR 0010 XOR 0011 XOR 0011 XOR 0100 XOR 0100 XOR 0101 XOR 0101 XOR 0110 XOR 0110 XOR 0111 -> (0001 XOR 0001) = 0000, 0010 XOR 0010 = 0000, 0011 XOR 0011 = 0000, 0100 XOR 0100 = 0000, 0101 XOR 0101 = 0000, 0110 XOR 0110 = 0 и 0111 ->

1 XOR 1 XOR 2 XOR 2 XOR 3 XOR 3 XOR 4 XOR 4 XOR 5 XOR 5 XOR 6 XOR 6 XOR 7 = 7

Исправленный и рабочий код

public class UniqueNumber {
  public static void main(String[] args) throws IOException {
    File file = new File("input-201.txt");
    Scanner scanner = new Scanner(file);
    List<Integer> list = new ArrayList<>();
    while(scanner.hasNextLine()) {
      Integer line = scanner.nextInt();
      list.add(line);
    }

    int ans = 0;
    for (int lineIndex = 0; lineIndex < list.size(); lineIndex++) {            
      ans ^= list.get(lineIndex);
    }
    System.out.println(ans);
 }
}

Чтение без файла

 Scanner scan = new Scanner(System.in);
 while (scan.hasNextLine()){
    Integer line = scanner.nextInt();
      list.add(line);
 }

на UNIX и Mac OS окончание ввода (обычно) CTRL+D, и на Windows CTRL+Z. scan.hasNextLine() вернёт false.

БЛОГ НА HUSL

Алгоритм поиска одного числа XOR

Ответы (1 шт):