Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Captain Shoaib : Civil War

By error26 · Limits 1s, 512 MB

Captain Shoaib is fighting against the zombies with his army. At some point, he realized that some of his soldiers are killing their own peers. After some investigation, he found some of his peers are actually imposter zombies and they are killing the original soldiers. To save his soldiers, Captain Shoaib needs to identify and kill the imposter zombies. But he doesn’t know how to identify the imposter zombies.

Captain Shoaib seeks help from Master Babu to save his army. Master Babu suggests a way to find the imposter zombies.

You are given an array strengthstrengthwhich denotes the strength of the soldiers. For any , if there is any strength[j]strength[j] where i!=ji != j and (strength[i]strength[j])==(strength[i]+strength[j])(strength[i] | strength[j]) == (strength[i] + strength[j]) then both of the ii and jj are zombies.

Captain Shoaib wants to find all the imposter zombies and kill them. As a friend of Shoaib, you should help him to find the imposter zombies. You need to print the indices of the imposter zombies so that Shoaib can kill all of them at once. If no imposter zombies are found, print -1 instead.


The first line contains an integer n (1n106)(1 ≤ n ≤ 10^6) — the number of soldiers as well as the imposter zombies. The second line contains n space-separated integers strength[0],strength[1],..,strength[n1]strength[0], strength[1], ….., strength[n-1](1strength[i]106)(1 ≤ strength[i] ≤ 10^6)— denoting the strengths of a soldier or a zombie.


Print the indices of the imposter zombies in ascending order. If no imposter zombies are found, print -1 instead.


6 8 10 8 9
0 1 3 4

The dataset is huge. Use faster I/O



    80% Solution Ratio

    YouKnowWhoEarliest, 3w ago

    MoRanSky.835291Fastest, 0.1s

    rfpermenLightest, 13 MB

    NirjhorShortest, 612B


    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.