basantCoder's blog

Dare2Compete coding challenge question. HELP???
By basantCoder, history, 3 years ago, In English

You start with 0 and you have to Find the minimum number of operations to reach 'n'. In one operation you can add or subtract any 2^k to your current number. Where k can be any positive integer.
Constraints:
test cases <200,000;
1 <= | n | <= 1,000,000,000 . Example:
INPUT:
First line is no. of test cases, then a single integer 'n' on each line.
5
1
2
0
6
10
OUTPUT:
1
1
0
2
2
Can anybody help??

  • Vote: I like it
  • -25
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by basantCoder (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Why not try to reach from n to 0 by subtracting nearest power of 2(floor) 

long long n,ans=0;
cin>>n;
while(n>0){
    n = n - pow(2,(int)__lg(n));
    ans++;
}
cout<<ans<<'\n';

Maybe Like this...Hope its not live Rn

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    its not always optimal!
    Like for 28 your code will give 3. But you can reach 28 is 2 operations also.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As any n can be represented in binary form which is nothing but sum of powers of 2. So the answer will be number of 1s in binary notation of n. Example: $$$10 = (1010)_2$$$ Here count of 1s = 2 = answer

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    for example take n=28, binary form = (11100)2
    According to your logic: answer = 3.
    But correct answer is 2. First operation add 32, second operation substract 4.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Your binary representation of 28 is wrong.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +2 Vote: I do not like it

      Sorry, I missed this case. I think we can always create consecutive 1's by subtracting

      $$$ 0 - 1 = 10 $$$

      (by taking a carry) in binary form, provided there is a 1 in the left.
      That is we can always replace continuous 1s with 2 operations, putting a 1 in the left and subtracting it by 1. Example: We want 1110

      $$$ 10000 - 10 = 1110 $$$

      So either it is 2 operations or (no of 1 bits) = x operations. We have to take minimum of it and sum all of such operations on consecutive 1s in the binary representation of n to get the answer.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    codinginveins Consider n=7 According to your logic it will give 3 , but the correct answer is 2 (Add 8 then subtract 1).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      https://mirror.codeforces.com/blog/entry/95133?#comment-841488

      I still dont know if I am missing something here.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        actually we can get cosecutive 1's and 0's format in 2 operations. Like is the number is (11111110000000)2. But still there can be complicated cases with random 1's and 0's where I am stuck.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 5   Vote: I like it 0 Vote: I do not like it

          $$$ 111000111000111000_2 $$$ can be divided and conquered as sum of answers of $$$ 111000_2 $$$, $$$ 111000000000_2 $$$ and $$$ 111000000000000000_2 $$$. Infact it will also be equivalent to

          $$$ ans(111000_2) + ans(111000_2) + ans(111000_2) = 3 * ans(111_2) $$$

          We just need to process the segments where we get 1s.
          ans(1) = 1 ans(11) = 2 ans(111) = 2 ans(1111) = 2 and so on

          → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it 

int recur(n){
    if(n == 0)
        return 0;
    else if((n & (n - 1)) == 0)
        return 1;
    int temp 1e9;
    for(int i = 0; i <= 14; i++){
        int val = abs(n - (1 << i));
        temp = min(temp, 1 + recur(val));
    }
    return temp;
}
void solve() {
    ll n;
    cin >> n;
    n = abs(n);
    cout << recur(n);

}

to reduce time complexity you can do memoization

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let, f(x) = Number of set bit's in binary representation of x. Answer will be min(f(x), f(-x)).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Had a hard time reading the title

→ Reply