getting wrong answer , need hint

An integer that can be represented in the form 2x+2y (where x and y are non-negative integers such that x≠y),
would have exactly two bits set in its binary representation.

For values up to 109, 32 bits is more than adequate; creating a look up table of these candidate numbers
(even by brute force) won't take any time at all.

Spoiler: http://coliru.stacked-crooked.com/a/0e1808c194529bfa
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <limits>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cassert>

// verify (at compile time) that the type unsigned int holds at least 32 bits
// https://en.cppreference.com/w/cpp/types/numeric_limits/digits
// https://en.cppreference.com/w/cpp/language/static_assert
static_assert( std::numeric_limits<unsigned int>::digits >= 32, "" ) ;

constexpr unsigned int NBITS = 32 ; // #bits required to cater to numbers up to 10^9

// verify (at compile time) that bits 1100 0000 0000 0000 0000 0000 0000 0000 is
// adequate to hold values up to 10^9 that the program requires
static_assert( ( (1U<<(NBITS-1)) + (1U<<(NBITS-2)) ) > 1'000'000'000, "" ) ;

// fill up the vector with numbers that have exactly two unique bits set
// where the lower bit position is at lower_bit_pos
void fill_higher_bit( unsigned int lower_bit_pos, std::vector<unsigned int>& target_numbers )
{
    const unsigned int low_bit_value = 1U << lower_bit_pos ;

    // for each bit position higher than lower_bit_pos set
    for( unsigned int pos = lower_bit_pos + 1 ; pos < NBITS ; ++pos )
        target_numbers.push_back( ( 1U << pos ) + low_bit_value ) ;
        // compute the integer value of the number and add it to the vector
}

std::vector<unsigned int> make_target_numbers()
{
    std::vector<unsigned int> numbers ;

    // for each possible bit position for which the less significant bit is set
    for( unsigned int lower_bit_pos = 0 ; lower_bit_pos < (NBITS-1) ; ++lower_bit_pos )
        fill_higher_bit( lower_bit_pos, numbers ) ;
        // fill the vector with all possible candidate numbers where a higher bit is set

    // look up for the nearest candidate number would be (slightly) faster
    // if the sequence is sorted; we can then do a binary search
    std::sort( numbers.begin(), numbers.end() ) ;
    return numbers ;
}

int main()
{
    const auto start = std::clock() ; // this is just for timing the creation of the look up table
    // may be commented out in production code
    // https://en.cppreference.com/w/cpp/chrono/c/clock
    // https://en.cppreference.com/w/cpp/chrono/c/CLOCKS_PER_SEC

    const std::vector<unsigned int> target_numbers = make_target_numbers() ;

    // these two lines may be commented out in production code
    const auto end = std::clock() ;
    std::cout << "creating the look up table (of size " << target_numbers.size() << ") took "
              << (end-start) * 1'000'000.0 / CLOCKS_PER_SEC << " microseconds.\n" ;

    // for each number in the initialiser list (the three given test cases,
    // and three more arbitrarily chosen numbers thousand, million and billion)
    for( unsigned int n : { 10U, 22U, 4U, 1000U, 1'000'000U, 1'000'000'000U } )
    {
        // https://en.cppreference.com/w/cpp/algorithm/lower_bound
        // get the (iterator to) the number in the candidate sequence greater than or equal to n
        const auto next = std::lower_bound( target_numbers.begin(), target_numbers.end(), n ) ;

        // if n is smaller than the smallest candidate number (3), we need to add one to n
        // *next - n times to bring the value up to the smallest candidate number
        // note that since next is the iterator, *next gives us the integer value of the number
        if( next == target_numbers.begin() ) std::cout << *next - n << '\n' ;
        else
        {
            // run-time sanity check; not required (we have already checked this via a static_assert)
            // comment out the next line in production code
            assert( target_numbers.back() > 1'000'000'000 ) ;

            // get the iterator to the candidate number that is just lower than n
            const auto prev = next-1 ;

            // the answer is the minimum of the distance between n and either of the two
            // candidate numbers. either add one to n (*next - n) times
            // or subtract one from n (n - *prev) times
            // https://en.cppreference.com/w/cpp/algorithm/min
            std::cout << std::min( *next - n, n - *prev ) << '\n' ; 
        }
    }
} 

http://coliru.stacked-crooked.com/a/83ec193e148dd263
I have an vector of pairs of final n along with problem no.Can anyone tell me what to do when n is same for 2 problem.How to print vector in such a way that larger index will get printed first.
Topic archived. No new replies allowed.