Dare2Compete coding challenge question. HELP???

Блог пользователя basantCoder

Автор basantCoder, история, 5 лет назад, По-английски

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??

basantCoder
5 лет назад
16

Комментарии (15)

Показать архивные | Написать комментарий?

basantCoder

5 лет назад, скрыть # |

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

→ Ответить

akash.garg2172

5 лет назад, скрыть # |

← Rev. 4 →

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

→ Ответить

basantCoder

5 лет назад, скрыть # ^ |

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

→ Ответить

codinginveins

5 лет назад, скрыть # |

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

→ Ответить

basantCoder

5 лет назад, скрыть # ^ |

← Rev. 3 →

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

→ Ответить

TheRealLeviAckerman

5 лет назад, скрыть # ^ |

Your binary representation of 28 is wrong.

→ Ответить

basantCoder

5 лет назад, скрыть # ^ |

Thanks for correcting

→ Ответить

codinginveins

5 лет назад, скрыть # ^ |

← Rev. 3 →

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.

→ Ответить

CoverDrive

5 лет назад, скрыть # ^ |

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

→ Ответить

codinginveins

5 лет назад, скрыть # ^ |

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

I still dont know if I am missing something here.

→ Ответить

basantCoder

5 лет назад, скрыть # ^ |

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

→ Ответить

codinginveins

5 лет назад, скрыть # ^ |

← Rev. 5 →

$$$ 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

→ Ответить

myth_

5 лет назад, скрыть # |

← Rev. 4 →


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

→ Ответить