# Lonely Integer

# Lonely Integer

Spartan300 + 19 comments Python's awesome

answer = reduce((lambda x, y: x^y), a)eiCheab6loSh3eix + 1 comment import operator

reduce(operator.xor, numbers)

SigmaSquared + 0 comments reduce(int.__xor__,numbers)

Mathcadd + 3 comments Ruby's faaaaaabulous

`a.reduce(&:^)`

Note that this code produces a smiley face, also.

prank7 + 2 comments How does this work?

xiaohanyu + 1 comment ruby's one line code golf:

gets and puts gets.split(/\s+/).map(&:to_i).reduce(:^)

sanamedio + 2 comments nums = raw_input().strip().split(" ")

print [int(x) for x in nums if nums.count(x)%2 != 0]

can someone make this into a one liner in python? :)

nort87 + 0 comments return Counter(b).most_common()[-1][0]

gahansaraiya + 1 comment why bother to take modulo? question says you have only 1 unique integers you can check nums.count(i) ==1 without calculating modulo

sanamedio + 0 comments :/ idk,lol

jjlearman + 0 comments See the xor trick explained below. Lambda and reduce are just ways to apply the operation iteratively and concisely. Using xor is the clever bit.

abitdodgy + 1 comment You don't actually have to convert this to a lambda. This should do:

`a.reduce(:^)`

margusmartsepp + 0 comments Still not even close to what you can do in J, Ursala, Mathematica or actually any programming language, that supports Tacit programming where this can be done in ~4 characters.

However I do understand the fustration of needing to write boiler-plate code for "popular" languages, ex: in c# this would look:

`static int LonelyInteger(IEnumerable<int> numbers) { return numbers.Aggregate(0, (subsum, next) => subsum ^ next); }`

griffk04 + 1 comment scala

(0/:a)(_^_)

satish_chippa + 1 comment Can you please explain this.

My scala solution

a.groupBy(x=>x).map(x=>(x._1,x._2.length)).filter(x=>x._2==1).keys.head

rox_gelsy + 1 comment you can also use XOR accumulative which will allow pass only the unique number. An XOR gate (sometimes referred to by its extended name, Exclusive OR gate) is a digital logic gate with two or more inputs and one output that performs exclusive disjunction. The output of an XOR gate is true only when exactly one of its inputs is true. (Wikipedia)

rox_gelsy + 0 comments Actually is the goal if this chapter bit manipulation.

none_da + 0 comments Mind blown

jaehoonlee88 + 0 comments You guys are genius.

williscool + 2 comments javascript

ar.reduce(function(a,b){ return a ^= b;}

numput + 0 comments a.reduce((x , y) => x ^ y)

Joestilllives + 1 comment What does ^ mean here?

Kanahaiya + 0 comments ^ represents Xor operation in program.

virus_mars + 0 comments d = raw_input()

reduce(lambda x, y : x^y, map(lambda x : int(x), list(d)))

margusmartsepp + 0 comments [deleted]kamanashisroy + 6 comments Now a days C++ is awesome too,

`return accumulate(a.begin(), a.end(), 0, [](int k, int i){ return k = k ^ i;});`

dgodfrey + 0 comments How does it work?

EDIT: Nevermind I know how it works now.

juaxix + 2 comments wow, this lambda expression is amazing :) That line equals to 5 at least! gj

int main() { int n; cin >> n; vector<int> A(n); for(int i=0;i<n;i++) cin >> A[i]; int num=0; for(int i=0;i<n;i++) if(count(A.begin(),A.end(),A[i])>1) continue; else { num = A[i]; break;} cout << num; return 0; }

narutoitachi329 + 0 comments complexity of count function is O(n),so your code complexity will become O(n^2)

#include <bits/stdc++.h> using namespace std; int dosome(int arr[], int n) { if(n==1) return 1; sort(arr,arr+n); for(auto i=0;i<n;) { if(arr[i]==arr[i+1]) i=i+2; else return arr[i]; } // return arr[n-1]; return 0; } int main() { int n; cin>>n; int arr[n]; for(auto j=0;j<n;j++) cin>>arr[j]; cout << dosome(arr, n) << endl; }

sorting required O(nlogn) complexity ,my Code Complexity will be O(nlogn+n)==O(nlogn)

tgnottingham + 2 comments Even better, use std::bit_xor.

return accumulate(a.begin(), a.end(), 0, bit_xor<int>{});

And in C++17, for large collections, it may be better to use std::reduce with potential parallelization and vectorization.

return reduce(execution::par_unseq, a.begin(), a.end(), 0, bit_xor<int>{});

elvis_dukaj + 0 comments I think you can write simply

`bit_xor<>{}`

instead of`bit_xor<int>{}`

PraneshASP + 0 comments [deleted]

moniba + 0 comments [deleted]elvis_dukaj + 0 comments [deleted]Crystal_star + 1 comment 1) please explain how accumulate is working here? 2) how vector is being traversed? please i am somewhat beginner to STL and don't know how these work..

viigihabe + 0 comments https://en.cppreference.com/w/cpp/algorithm/accumulate The possible implementation of it is also shown. Look into https://en.cppreference.com/w/cpp/algorithm and you'll see lots of useful functions. Although, note that examples there tend to be really academic.

abhishek106 + 1 comment this doesnt work. Can you explain it?

yulia_ekb + 0 comments See help section - Caching

satyasri12511001 + 2 comments please tell me why this code is not working its perfectly working in my computer(python ide 3.4)

n=int(input()) a=[] for i in range(n): a.append(int(input())) for i in range(n): if a.count(a[i])<2: print(a[i])

alphasingh + 0 comments I reckon you're new to python. See, when the array is provided at input in a single line, we cannot take the input like this, i.e. You're taking whole line as an input and storing this whole line in the array

*a*, after the first input, it will show errors because only one line of input is available, while you're asking for n continouos lines. So, The best method is to use list(**map()**) or/and**input().split()**to store array elements given in a single line. Hope this helps :)rox_gelsy + 0 comments see the xor truth table and resolve with xor. Actually is the goal if this chapter bit manipulation

satyasri12511001 + 0 comments please tell me why this code is not working its perfectly working in my computer(python ide 3.4)

n=int(input()) a=[] for i in range(n): a.append(int(input())) for i in range(n): if a.count(a[i])<2: print(a[i])

gitblame + 1 comment Java8:

`Arrays.stream(a).reduce(0, (x,y) -> x^y);`

snaran + 0 comments There's also no need to store the array 'a'. We can just read a number from stdin, XOR it, and continue the loop. How might you do this in Java 8? Is there a standard way to convert System.in into a stream of the next N integers?

tjano + 0 comments Scala:

new java.util.Scanner(System.in) match { case sc => println ((0 until sc.nextInt).map(_ => sc.nextInt).reduce(_ ^ _)) }

tamsoftware + 0 comments Swift:

a.reduce(0, ^)

janusz_k + 0 comments Java 8

return IntStream.of(a) .reduce(0, (e, accumulator) -> e ^ accumulator);

hualing_yu + 0 comments This is genious...

niwsa22 + 1 comment can someone explain how it works?

gahansaraiya + 0 comments there is lot in the comment section too what you didn't understand?

jeet_txt + 0 comments nice

Kanahaiya + 0 comments Here is the video explaination of my solution using XOR trick in O(n) time -

and you can find most of the hackerrank solutions with video explaination here- https://github.com/Java-aid/Hackerrank-Solutions

and many more needs to be addeed.

Any comments and feedback would be really appreciated.

Regards,

Kanahaiya Gupta

Git Hub URL | https://github.com/Java-aid/

LIKE US | https://www.facebook.com/javaaid/

SUBSCRIBE US | https://goo.gl/jziyfZ

TELEGRAM LINK| @javaaid">@javaaid">https://web.telegram.org/#/im?p=@javaaid

mkmgames + 2 comments Whoa, this XOR solution was really an eye-opener to me. Before this, I always programmed stuff "inside a box". Now I know I can (and I will try harder to) connect everything I've learned - mathematics, computer science, digital logic etc.

xshuai + 5 comments I have a O(n) solution but I need to use a set so the space complexity is O(n). I think the optimal solution requires bit manipulation? can you provide that?

shashank21jHackerRank Admin + 1 comment a^a = 0

and a^0 = a

so if you have an element repeated 2n times, it's xor is 0. and the lonely element remains as it is.rox_gelsy + 0 comments yes is the goal of this chapter the bit manipulation. And xor it is nice because it return 1 when inputs are different

Salaikumar + 1 comment Can u help me to write a O(n) solution? I just sorted the array and looped over it again using simple compare to find the element. The solution got accepted and passed all the test cases. @Shashank21j, Before applying the xor operation, the input needs to be sorted right?

rox_gelsy + 0 comments bit manipulation, xor

shashank21jHackerRank Admin + 12 comments No need to sort

`a = 0 \\initialise for (i=0;i<n;i++) { cin >>b; a ^= b; } cout<<a;`

chiragvartak + 1 comment I don't seem to grasp the logic behind this piece of code. How does successively xor-ing the inputs with a does the job? It seems to me that you have assumed that the inputs will be entered in an ascending order. Correct me if I am wrong.

wchargin + 12 comments Nope, this should work. Note that if you take

`a ^ a`

, you will always get`0`

. Furthermore, if you take`a ^ x ^ a`

, you will always get`x`

. Therefore, all the pairs of numbers will cancel out. For example, if you have`n = 9`

and`A = {4, 9, 95, 93, 57, 4, 57, 93, 9}`

, then you will effectively by computing the value of`4 ^ 9 ^ 95 ^ 93 ^ 57 ^ 4 ^ 57 ^ 93 ^ 9`

. It doesn't matter what order you take the xors, so this is equivalent to`(4 ^ 4) ^ (9 ^ 9) ^ (95) ^ (93 ^ 93) ^ (57 ^ 57)`

, which is`0 ^ 0 ^ 95 ^ 0 ^ 0`

, or just`95`

.Jitendra414 + 1 comment but we are taking input's one by one so how come the sum^=temp will provide the solution.

jason_goemaat + 2 comments All numbers except for 1 will be in pairs. xoring a value with the same number twice will reset all the flipped bits back to their original position. Therefore you start with 0 and xor every number that comes in. If a number occurs twice, the second xor will reflip the bits the first xor flipped. You will be left with the answer because it is the only number that flipped bits only once. It doesn't matter if other numbers flipped those bits in the mean time, as long as they came in pairs they will reset themselves. It's like simple XOR encryption.

ceqi90 + 0 comments Very nice and clear explanation!

achuthakrishnan + 0 comments it looks like magic to me!

chiragvartak + 2 comments Wow! I really loved this. It is really fascinating how the result of XOR stores the 'data' of which numbers were XORed to get the number. Some might take this for granted, but this trick really blew my mind!

savras + 0 comments Indeed! Took me a while to grasp and come to terms with the concept.

niuworld + 0 comments thanks for your idea!

Sniffy + 0 comments crap that solution does work and is insidiously simple. not a real-life problem though.

sagar122 + 0 comments awesome solution.... thanks.

gibibit + 0 comments That was so cool!

afshinmeh + 0 comments Great explanation.

Xploiter_coder + 0 comments great explanation.It really helped me.

sangupta007 + 0 comments thank you so much

satadhi + 0 comments best explaniation ever thank you mam !

vinod_biet + 0 comments very nice explanation wchargin keep it up..

einsteinFan + 0 comments Great Really great trick

Jitendra414 + 2 comments but if we don't sort then how will it give the answer because in the input's 0 0 1 2 1. 0 ^ 0= 0, 0 ^ 1 = 1, then 1 ^ 2 will be what?

abhiranjan + 0 comments Hi @Jitendra414,following two properties are useful.

`Xor`

operations are commutative, i.e., a^b^c = a^c^b = b^a^c = b^c^a = c^a^b = c^b^a- a ^ a = 0

dsouzavinil29 + 1 comment Hi Jitendra414,

1^2=3

1 in binary is 01

2 in binary is 10

XOR of 01 and 10 = 11,

11 is 3 in decimal

And then your next input is 1

1^3=2

Hence the answer is 2

kavishme + 0 comments fundamentals.:)

tsasaa + 4 comments Amazing! It's working!

`int result = 0; for (int i = 0; i < a.length; i++) { result = result ^ a[i]; } return result;`

Noyaux + 0 comments I think you can use ^= to reduce : result = reduce

d24amazon + 0 comments [deleted]kalbatprog7 + 0 comments Can you please explain how this works? please?

zehnnexus + 0 comments Genius. Thanks!

niuworld + 0 comments This is amazing ! thanks so much!

zerodivisible + 0 comments Awesome idea.

Kennes + 0 comments Awesome

CodingFrank + 0 comments Cool~Xor is a powerful tool to solve the problems like this problem

rashmu_jho + 0 comments awesum!!!

jaihoon + 0 comments What if the input is 0, 0 ?

Piyush89 + 0 comments xor the array you will get the digit with single occurence.

int xor = a[0];

for(int i=1; i

return xor;

brentonstrine + 1 comment What does

`O(n)`

mean?jason_goemaat + 0 comments That the time (or space) the algorithm requires is linear with relation to the number of elements being processed. For every x inputs you have to perform some multiple of x operations. If you have 1,000,000 inputs then it should take roughly 1,000 times as long as if you have 1,000 inputs. O(N

^{2}) means the time it takes increases exponentially with the number of inputs, so 1,000,000 inputs might take 1,000,000 times as long as 1,000 inputs.

RodneyShag + 3 comments ### Java solution - passes 100% of test cases

O(n) runtime. O(1) space. Uses XOR. Keep in mind:

- x ^ x = 0
- x ^ 0 = x
- XOR is commutative and associative

public static int lonelyInteger(int [] array) { int val = 0; for (int num : array) { val = val ^ num; // ^ is XOR operator } return val; }

From my HackerRank Java solutions.

SanketJain + 1 comment cannot beat this. What a logic!

RodneyShag + 2 comments Thanks. I had first heard of this problem over a dinner conversation. The solution is now ingrained in my memory.

shreyagoel181 + 0 comments [deleted]kunnu120 + 1 comment What XOR means? and can you please explain me I didn't get it how it works.

RodneyShag + 1 comment XOR is

**true**if the 2 bits being xored are different, and**false**otherwise.kunnu120 + 0 comments Thanks for the reply. very Nice logic

kunnu120 + 1 comment Damn!! did you come up with this logic? Amazing, It took me so much time to do this problem still I didn't get it.

RodneyShag + 0 comments I think I was told this solution over a dinner conversation a few years ago.

abhinavsagar + 0 comments [deleted]

ameyanator + 3 comments People are using many techniques but i consider the easiest to be XOR gate.This question is meant to be solved using Xor gate. Here is my Code-

#include <iostream> using namespace std; int main() { int n; cin>>n; int ans=0; for(int i=0;i<n;i++) { int x; cin>>x; ans^=x; } cout<<ans<<endl; }

RamiRe + 0 comments Salute!>

khadar111 + 0 comments Why is this not sinking in my head?! Btw my solution is pretty much the same length but I feel so deprived by not getting a "feel" of XOR.

Arpit_tiwari + 0 comments genious|||||||||||||

wlsc1 + 0 comments Beautiful and fast Java solution:

public class Solution { private static int lonelyInteger(int[] a) { int value =0; for(int i=0; i<a.length; i++){ value ^= a[i]; } return value; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } System.out.println(lonelyInteger(a)); } }

omrigotlieb + 5 comments Java Solution: Easy way is to use XOR operation: sum ^= a[i]; By doing so every paired number will become 0 and sum will remain the unique number.

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { private static int lonelyInteger(int[] a) { return 0; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] a = new int[n]; int sum = 0; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); sum ^= a[i]; } //System.out.println(lonelyInteger(a)); System.out.println(sum); } }

adelin_ghanayem + 1 comment This is why I love Hackerrank ...

omrigotlieb + 0 comments Any time :)

snaran + 0 comments It's good, but why are you storing the integer read? Hacker rank allows you to change the boiler plate code that they wrote, and you can do

for (int i=0; i<n; i++) { sum ^= in.nextInt(); }.

sourav47 + 0 comments [deleted]sourav47 + 0 comments [deleted]sourav47 + 0 comments will u explain that step by step?plz

Lyanna + 0 comments My favorite challenge here so far! Was happy like a kid in a candy shop when got the idea. No need for lambdas or sets, XOR result itself stores the answer.

madhuri11 + 0 comments Just by xoring the whole array gives the unique element. Here is my code

int uniqueEle=a[0]; for(int i=1;i<a.length;i++) { uniqueEle^=a[i]; } return uniqueEle;

gragest + 0 comments Really quick and simple solution using C#, sadly to my knowledge c# doesnt have a reduce function built in.. :(

static int lonelyinteger(int[] a) { List<int> occured = new List<int>(); foreach(int x in a){ if(!occured.Contains(x)){ occured.Add(x); } else { occured.Remove(x); } } return occured[0]; }

Sort 254 Discussions, By:

Please Login in order to post a comment