Форум программистов, компьютерный форум CyberForum.ru

Найти пары элементов массива сумма которых является степенью двойки - C++

Восстановить пароль Регистрация
 
netrox
 Аватар для netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 61
Завершенные тесты: 2
30.07.2016, 11:02     Найти пары элементов массива сумма которых является степенью двойки #1
Вам задано n чисел a1, a2, ..., an. Найдите количество пар индексов i, j (i < j) таких, что ai + aj является степенью двойки (то есть найдется такое целое число x, что ai + aj = 2x).
Входные данные
В первой строке следует целое положительное число n (1 ≤ n ≤ 105) — количество чисел.

Во второй строке следует n целых положительных чисел a1, a2, ..., an (1 ≤ ai ≤ 109).

Выходные данные
Выведите количество пар индексов i, j (i < j) таких, что ai + aj является степенью числа 2
Миниатюры
Найти пары элементов массива сумма  которых является степенью двойки   Найти пары элементов массива сумма  которых является степенью двойки  
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2016, 11:02     Найти пары элементов массива сумма которых является степенью двойки
Посмотрите здесь:

C++ Определить, является ли данное число степенью двойки
Найти такие пары натуральных чисел, сумма которых является квадратом некоторого натурального числа C++
Найти из массива пары чисел, сумма которых укладывается в определенном диапазоне C++
C++ Является ли число степенью двойки?
C++ Является ли число степенью двойки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
netrox
 Аватар для netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 61
Завершенные тесты: 2
30.07.2016, 11:04  [ТС]     Найти пары элементов массива сумма которых является степенью двойки #2
Мой код оказался медленным:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include"iostream"
using namespace std;
 
int main()
{
 
    int n, mas[100000];
    int pair = 0;
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        cin >> mas[i];
    }
 
    for (int k = 0; k< n - 1; k++)
    {
        for (int j = k + 1; j<n; j++)
        {
            for (int v = 2; v<1000000000; v = v * 2)
            {
                if ((mas[k] + mas[j]) == v)
                {
                    ++pair;
                                         break;
                     
                }
            }
        }
    }
    cout << pair;
}
netrox
 Аватар для netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 61
Завершенные тесты: 2
30.07.2016, 11:11  [ТС]     Найти пары элементов массива сумма которых является степенью двойки #3
В вопросе не приписал степени
Миниатюры
Найти пары элементов массива сумма  которых является степенью двойки  
Изображения
 
MansMI
1046 / 843 / 205
Регистрация: 08.01.2012
Сообщений: 3,021
30.07.2016, 11:28     Найти пары элементов массива сумма которых является степенью двойки #4
mas[k] + mas[j] можно посчитать один раз,
и массив 20-230 можно подготоаить заранее, возможно поможет
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,155
Завершенные тесты: 1
30.07.2016, 13:29     Найти пары элементов массива сумма которых является степенью двойки #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;
 
bool is_power2(int k)
{
    int count1=0;
    while(k)
    {
        count1+=(k&1);
        k>>=1;
    }
    return !(count1-1); // должна быть всего одна единичка
}
int main()
{
 
    int n;
    cin >> n;
    int* mas=new int[n];
    for (int i = 0; i<n; i++)
    {
        cin >> mas[i];
    }
 
    int pair = 0;
    for (int k = 0; k< n - 1; k++)
    {
        for (int j = k + 1; j<n; j++)
        {
            if( is_power2(mas[k] + mas[j]) )
                ++pair;
        }
    }
    delete[] mas;
    cout << pair<<endl;
    system("pause");
    return 0;
}
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 584
Завершенные тесты: 2
31.07.2016, 16:39     Найти пары элементов массива сумма которых является степенью двойки #6
C++
1
x & (x-1) == 0
простая проверка на степень 2-ки
netrox
 Аватар для netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 61
Завершенные тесты: 2
31.07.2016, 20:17  [ТС]     Найти пары элементов массива сумма которых является степенью двойки #7
mat_for_c, MansMI, Спасибо за помощь , конечно оба варианта рабочие, но на codeforces всё равно выдаёт, что превышено ограничение времени
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
31.07.2016, 21:24     Найти пары элементов массива сумма которых является степенью двойки #8
Цитата Сообщение от netrox Посмотреть сообщение
mat_for_c, MansMI, Спасибо за помощь , конечно оба варианта рабочие, но на codeforces всё равно выдаёт, что превышено ограничение времени
А кто тогда навесил "лучший ответ" на сообщение №5, оно же не проходит по времени?
MansMI
1046 / 843 / 205
Регистрация: 08.01.2012
Сообщений: 3,021
31.07.2016, 21:36     Найти пары элементов массива сумма которых является степенью двойки #9
5Г вариантов, даже простой перебор индексов без вычислений не укладывается
netrox
 Аватар для netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 61
Завершенные тесты: 2
31.07.2016, 21:39  [ТС]     Найти пары элементов массива сумма которых является степенью двойки #10
Mr.X, Ну ведь не я
Миниатюры
Найти пары элементов массива сумма  которых является степенью двойки  
netrox
 Аватар для netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 61
Завершенные тесты: 2
31.07.2016, 21:41  [ТС]     Найти пары элементов массива сумма которых является степенью двойки #11
Mr.X,
Миниатюры
Найти пары элементов массива сумма  которых является степенью двойки  
netrox
 Аватар для netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 61
Завершенные тесты: 2
31.07.2016, 21:44  [ТС]     Найти пары элементов массива сумма которых является степенью двойки #12
MansMI,
MansMI
1046 / 843 / 205
Регистрация: 08.01.2012
Сообщений: 3,021
31.07.2016, 21:55     Найти пары элементов массива сумма которых является степенью двойки #13
чего?
netrox
 Аватар для netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 61
Завершенные тесты: 2
31.07.2016, 22:16  [ТС]     Найти пары элементов массива сумма которых является степенью двойки #14
MansMI, прости , сайт заглючил
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2016, 23:19     Найти пары элементов массива сумма которых является степенью двойки
Еще ссылки по теме:

Является ли число степенью двойки C++
C++ Является ли натуральное число точной степенью двойки
C++ Проверить, является ли число степенью двойки

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Новичок
Модератор
 Аватар для Новичок
1137 / 708 / 148
Регистрация: 17.07.2012
Сообщений: 4,039
Записей в блоге: 1
Завершенные тесты: 2
31.07.2016, 23:19     Найти пары элементов массива сумма которых является степенью двойки #15
Сообщение было отмечено автором темы, экспертом или модератором как ответ
N <= 105
Очевидно же, что в лоб никак не зайдет. Нужно использовать map, насчитать количество каждого числа, а затем пройтись по нему и вычислить ответ используя комбинаторные формулы. Степени двойки предварительно насчитать. Идем по map и скажем видим число 1, тогда надо найти число 2 - 1 = 1, 4 - 1 = 3, 8 - 1 = 7... И дальше перемножить количества этих чисел и чтоб не было повторений поделить на 2. Если само число является степенью двойки то надо еще в ответ добавить количество комбинаций между равными числами. Ну например есть 3 двойки, 2 + 2 = 4 степень двойки, значит надо добавить в ответ 3 * (3 - 1) / 2. Вот такой код заходит.
Код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//GNU C++11
#include <bits/stdc++.h>
 
using namespace std;
using int64 = long long;
using uint64 = unsigned long long;
 
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); // Эти 2 строки для ускорения ввода, порой в олимпиадных задачах без них решение может упасть по времени
    uint64 n;
    cin >> n;
    map <int64, uint64> cnt;
    for (uint64 i = 0; i < n; i++) {
        int64 t;
        cin >> t;
        cnt[t]++;
    }
    vector <int64> pow2;
    for (int64 p = 1, h = 1e18; p <= h; p *= 2) pow2.push_back(p); // Степени двойки
    uint64 ans = 0;
    for (auto& i: cnt) {
        for (auto& j: pow2) {
            if (j == 2 * i.first) {
                ans += i.second * (i.second - 1);
                continue;
            }
            auto it = cnt.find(j - i.first);
            if (it != cnt.end())
                ans += it -> second * i.second;
        }
    }
    cout << ans / 2;
}
Yandex
Объявления
31.07.2016, 23:19     Найти пары элементов массива сумма которых является степенью двойки
Ответ Создать тему
Опции темы

Текущее время: 13:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru