'How to improve the code to return the unpaired element
I am practising for an upcoming coding interview and here is one of my practice problems and my progress.
How can I improve the program and what is your advice?
Also, are there any cities that could help with improving my coding skills?
Question:
A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.
For example, given array A such that:
A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.
Assume that:
N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Solution:
import java.util.*;
public class Solution {
public int solution(int[] A) {
int x;
for(int i = 0; i < 7; i++)
{
//create an integer array containing an odd number of elements of numbers ranging from 1 - 1,000,000
//for(int N = 1; N <= 1,000,000; N++)
int N = 1;
while(N > 1 && N <= 1000000)
{
//check if N is odd then assign to the array
if(N != N/2)
{
A[i] = N;
}
}
//check for any element not paired more than once
if(A[i] != A[i++])
{
x = A[i];
}
else
return 0;
}
//return unpaired elemnent
return x;
}
}
Solution 1:[1]
Something like this should work, here I implemented it in a way where I test all ints it gets against the rest, and only return if there is a solution (note there has to be a default, maybe a better way to handle "no solutions".
public class Solution {
public int solution(int[] A) {
boolean possibleSolution = true; // to return and properly break if not possible
for(int i = 0; i < A.length; i++) // run for all ints
{
possibleSolution = true; // set possible true, in case last one failed
for(int j = 0; j < A.length; j++) // take all ints again (to compare to the rest
if(A[i] == A[j] && i != j){ // note i escape comparing to itself
possibleSolution = false; // if there is a math it can't be this one
break; // break to save resources
}
if(possibleSolution) // if it's the solution
return A[i]; // return the current number (from the initial array as that is the reference number and the 2nd is for comparing)
}
return 0; // return default
}
public static void main(String[] args){
Solution solution = new Solution(); // instance
int[] ints = {9,3,9,3,9,7,9}; // new values
System.out.println(solution.solution(ints)); // print the method after it was run
}
}
Note that adding the ints, is not included here unsure what types of values is needed
but simply add them and then pass the array, if multiple answers are possible, then instead of return add to a List<Integers> results = new ArrayList<>();, and after all i is run through return the resultsthis would be where the return 0; is at the moment.
Solution 2:[2]
The accepted solution violates the requirement:
expected worst-case time complexity is O(N)
as it has a quadratic complexity (two nested loops). An obvious fast solution would use a HashSet<Integer> for remembering the yet unpaired numbers. But this would violate the other requirement:
expected worst-case space complexity is O(1)
There's a simple trick satisfying both:
public int solution(int[] A) {
int result = 0;
for (int x : A) result ^= x;
return result;
}
This uses the fact, that x ^ x == 0 for any x and the associativity of ^. This means that any pair of equal values cancels out, what remains is the single unpaired value (in case of multiple unpaired values, the result makes no sense; such a case can't be detected).
The accepted solution by Mikenno is wrong. For the input {1, 1, 1} there's a pair of ones and an unpaired one, so the result should be 1, but it returns 0.
Solution 3:[3]
This answer was tested on Codility and it got 100% for performance and correctness.
What I am doing is:
Sorting the array so the pairs will get together therefore i will be able to check every two pairs in the array by iterating through it.
Then I am adding 2 to both indexes to get the next pair and so on.
The first mismatch means we've got our target as the two indexes are pointing to pairs.
Here is the code:
public static int solution (int[] x) {
int found = 0;
int i = 0;
int j = 1;
Arrays.sort(x);
//To sort the array so if you have {9 , 3 , 9 , 3 , 9 , 7 , 9}
//it will be { 3 , 3 , 7 , 9 , 9 , 9 , 9}
if (x.length == 1) {
found = x[0];
}
while (x.length % 2 == 1 && i < x.length && j < x.length) {
if (x[i] == x[i+1]) {
i = i + 2;
j = j + 2;
} else {
found = x[i];
break;
}
}
if (found == 0 && i == x.length-1) {
found = x[i];
}
return found;
}
Solution 4:[4]
my try :)
public int solution(int[] arr) {
if (arr.length == 1) return arr[0];
Arrays.sort(arr);
int odd = -1;
for (int i = 0; i < arr.length; i++) {
if (i == arr.length-1) {
odd = arr[i];
break;
}
if (arr[i] == arr[i + 1]) {
i++;
continue;
}
odd = arr[i];
}
return odd;
}
Solution 5:[5]
That is my solution in Python, it has O(N) or O(N*log(N)) as per Codility test results. It's very simple.
def solution(A):
A=sorted(A)
return abs(sum(A[::2])-sum(A[1::2]))
So, I just sorted the array and added up all the even positions of the array and subtracted from the sum of all the odd positions in the array, this difference is the result.
Solution 6:[6]
This code achieved 100% correctness and performance
public int solution(int[] A) {
// write your code in Java SE 8
if (A.length == 0){
return 0;
}
if (A.length == 1) {
return A[0];
}
Arrays.parallelSort(A);
for(int i=0; i<A.length-2; i+=2) {
if(A[i]!=A[i+1])
return A[i];
}
return A[A.length-1];
}
Solution 7:[7]
One solution is to use a dictionary(key, value). Solution in swift :
let arr:[Int] = [1, 2, 3, 2, 4, 5, 4, 1, 3]
var valuesDict:[Int:Int] = [:]
for num in arr {
if let value = valuesDict[num] {
valuesDict[num]! += 1
} else {
valuesDict[num] = 1
}
}
print(valuesDict)
var unpairedElement:Int?
for (key, value) in valuesDict {
if value == 1 {
unpairedElement = key
break
}
}
print("unpaired element is \(unpairedElement!)")
Solution 8:[8]
100% PASS:
import java.util.Hashtable;
class Solution {
public int solution(int[] A) {
if (A.length == 0){
return 0;
}
if (A.length == 1) {
return A[0];
}
Hashtable<Integer, Integer> occurrences = new Hashtable<Integer, Integer>();
for(int i=0; i< A.length; i++)
{
if (occurrences.containsKey(A[i]))
{
occurrences.remove(A[i]);
}
else
{
occurrences.put(A[i], 1);
}
}
// find unpaired element
for(Map.Entry<Integer, Integer> entry: occurrences.entrySet())
{
if(entry.getValue() == 1)
{
return entry.getKey();
}
}
return 0;
}
}
Solution 9:[9]
I know that this is not java, it is PHP but the login can be applied anywhere, and I didnt see that kind of solution here:
function solution($A) {
sort($A); //sort the array
$arrString = implode("-",$A); // make the string
foreach($A as $a):
$str = (string)$a . '-' . (string)$a; // generate the string we will search
if (strpos($arrString, $str) === false) return $a; //if the string dont exist return the number
endforeach;
}
Solution 10:[10]
Very simple, correct and efficient solution in ruby
def solution(a)
hash = {}
a.each do |n|
if hash[n]
hash.delete(n)
else
hash[n] = 1
end
end
hash.keys.first
end
Solution 11:[11]
Solution in Swift 100% pass - detected time complexity: O(N) or O(N*log(N))
import Foundation
import Glibc
// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 4.2.1 (Linux)
var dict = Dictionary<Int, Int>()
if A.count == 1 { return A[0] }
for i in 0..<A.count {
if dict.keys.contains(A[i]) {
dict[A[i]] = nil
}
else {
dict[A[i]] = 1
}
}
for (k,v) in dict
{
if v == 1 {
return k
}
}
return 0;
}
Solution 12:[12]
The solution in swift 55% accuracy
public func solution(_ A : inout [Int]) -> Int? {
let sorted = A.sorted()
var hashmap = [String: Int]()
for value in sorted {
let key = String(describing: value)
if (hashmap[key] != nil) {
hashmap[key]! += 1
} else {
hashmap[key] = 1
}
}
for (key, value) in hashmap {
if value == 1 {
return Int(key) ?? 0
}
}
return nil
}
Solution 13:[13]
RUBY 100% all:
def solution(a)
summ = 0
rrr = 1
a.sort.each do |el|
summ = summ + el * rrr
rrr = -rrr
end
summ
end
Solution 14:[14]
All the solutions that are using SORT will end up running in O(N log N) time.
Below is the optimal way that runs in O(N) time with O(N) space complexity. However, space complexity could further be optimized using bitwise operations.
The below code is using a hash table and storing the occurrences of each element of A[] as key-value pairs. After that, a loop runs through all the key-value set and check if any occurrence is not an even number, meaning no pair.
public int solution(int[] A) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(Integer a : A) {
if(hashMap.containsKey(a)) {
hashMap.put(a, hashMap.get(a)+1);
} else {
hashMap.put(a, 1);
}
}
for(Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
if(entry.getValue() % 2 == 1) {
return entry.getKey();
}
}
return 0;
}
Solution 15:[15]
Javascript solution with O(N*logN), pass all tests 100%
function solution(A) {
let mapObject={}
for(let i=0;i<A.length;i++){
if(mapObject[A[i]])
{
delete mapObject[A[i]]
}else{
mapObject[A[i]]=A[i];
}
}
return Object.values(mapObject)[0];
}
Solution 16:[16]
Here is the Python code, it has O(N) or O(N*log(N)) as per Codility test results. Feel free to ask questions )
def solution(A):
# write your code in Python 3.6
odd = -1
if len(A) == 1:
return A[0]
A.sort()
i = 0
while i<len(A):
if i == len(A) - 1:
odd = A[i]
break
if A[i] == A[i+1]:
i+=2
continue
odd = A[i]
i+=1
return odd
Solution 17:[17]
in Java you could obviously use a HashSet, which is fast but requires much space:
public int solutionOk(int[] A) {
Set<Integer> set = new HashSet<>();
for (int a : A) {
if (!set.remove(a)) {
set.add(a);
}
}
return set.stream().iterator().next();
}
but it will be much easier, and faster to use XOR operation:
public int solution(int[] A) {
return Arrays.stream(A).reduce(0, (a, b) -> a ^ b);
}
It is an old trick to save memory in LinkedLists. It was used to XOR memory addresses with each other, to save 4 bytes of memory. This trick can also be used to find parity. Instead of storing the values we just XOR every element of the list, with the next. The one that doesn't have a pair, is left at the end.
Solution 18:[18]
My PHP Code result 100%
// write your code in PHP7.0
if(count($A) == 0){ return 0; }
if(count($A) == 1){ return $A[0]; }
sort($A);
for($i = 0; $i <= count($A); $i = $i+2){
if($i+1 == count($A)){ return $A[$i]; }
if($A[$i] != $A[$i+1]){ return $A[$i]; }
}
Solution 19:[19]
This solution worked.
`Set<Integer> org = new HashSet<Integer>();
List<Integer> lit = new LinkedList<Integer>();
int finalVal = 0;
for(int ab : A) {
org.add(ab) ;
lit.add(ab) ;
}
System.out.println(org.toString());
for(int fg : org) {
int df = lit.stream().filter(s -> s == fg).collect(Collectors.toList()).size();
if (df%2 == 1) {
System.out.println("Final -"+ fg);
finalVal = fg;
break;
}
System.out.println(fg +" -"+ df);
}
return finalVal;`
Solution 20:[20]
Swift solution
public func solution(_ A : inout [Int]) -> Int {
return A.reduce(0, ^)
}
Something like this should work, Detected time complexity: O(N) or O(N*log(N))
Solution 21:[21]
Here is my python implementation
Detected time complexity: O(N) or O(N*log(N))
def solution(A):
unmatched = {}
for item in A:
if item not in unmatched:
unmatched[item] = 1
else:
unmatched.pop(item, None)
for k in unmatched:
return k
Solution 22:[22]
Hi I come across with this answer
import java.util.*;
class Solution {
public int solution(int[] A) {
Arrays.sort(A);
int ctr = 1, result = 0;
for (int x = 0; x < A.length - 3; x+= 2){
if(A[x] != A[ctr] && A[ctr] == A[ctr+1] ){
return A[x];
}
ctr +=2;
}
return A[A.length-1];
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow