1

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;
    }
}
1

23 Answers 23

36

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.

3
  • 4
    this should be the accepted solution by and far esp. since it shows an ideal way to leverage and understand XOR logic. Nov 21, 2018 at 0:31
  • 4
    OMG. Amazing. Amazing.
    – Basil Musa
    Jul 4, 2019 at 18:49
  • 1
    this solution is amazing, this should be the accepted solution and by far the best solution. May 22, 2021 at 6:36
5

This answer was tested on Codility and it got 100% for performance and correctness.

What I am doing is:

  1. 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.

  2. Then I am adding 2 to both indexes to get the next pair and so on.

  3. 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;
}
3
  • Would you add some explanation to this? Readers will find it easier to understand answers that are accompanied by some explanation.
    – halfer
    Feb 14, 2019 at 0:06
  • @maaartinus also gets 100% on Codility, and is a simpler solution.
    – James Ray
    Feb 28, 2019 at 1:51
  • Arrays.sort(x) is bottleneck and makes the solution O(N log N). The optimal way to solve this yields O(N).
    – ihaider
    May 21, 2020 at 14:12
3

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; 
}
3
  • I like you use Arrays.sort()
    – aljx0409
    Jul 16, 2019 at 0:22
  • I have 100% on Codility Jul 16, 2019 at 0:55
  • your code will return the last element in the sorted array
    – Vignesh
    Jun 22, 2021 at 13:23
3

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];
}
3

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.

1

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!)")
1

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;
}

}

0

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.

3
  • you enabled a better understanding of the requirement. Great solution
    – Atinuke
    Mar 28, 2017 at 2:03
  • 4
    This answer is incorrect. This doesnt address cases like {1, 1, 1}. @maaartinus's answer is correct.
    – pahan
    Oct 31, 2018 at 9:16
  • this is brute force implementation. Please do no use if considering optimal solution.
    – ihaider
    May 21, 2020 at 14:11
0

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;
}
0

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
0

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;
}
0

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
}
0

RUBY 100% all:

def solution(a)

  summ = 0
  rrr = 1

  a.sort.each do |el|

    summ = summ + el * rrr
    rrr = -rrr

  end
  summ

end
0

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;
}
0

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];

}

0

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
0

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.

0

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]; }    
}    
0

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;`
1
  • Please add further details to expand on your answer, such as working code or documentation citations.
    – Community Bot
    Aug 29, 2021 at 15:37
0
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))

0

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
0

Here is my answer in javascript

function solution(A) {
for (let i = 0; i < A.length; i++) {
    let check = A.filter((item) => item == A[i])
    if (check.length == 1) {
        return check[0]
    }
}
}
-1

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];
}

}
1
  • Oh sorry Thank you for that. (Y) Feb 23, 2019 at 9:34

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.