basantCoder's blog

Dare2Compete coding challenge question. HELP???
By basantCoder, history, 5 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?
»
5 years ago, hide # |
 
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
»
5 years ago, hide # |
← 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
»
5 years ago, hide # |
 
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
  • »
    »
    5 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      5 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      Your binary representation of 28 is wrong.

      → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
      ← 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
  • »
    »
    5 years ago, hide # ^ |
     
    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
»
5 years ago, hide # |
← 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
»
5 years ago, hide # |
 
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
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Had a hard time reading the title

→ Reply