CareerCup

Here is my implementation for this problem:

basicalgos.blogspot.com/2012/03/34-find-outlier-pattern-in-array.html

You need to check first 3 repetition for the pattern. then only check first characters of pattern skipping the remaining. If the next pattern char is same as previous check remaining char ahead if they don't resemble the same pattern you got the erroneous one...

* Make a simple hash array to find the number of times each digit has been found.
* Find the pattern of repetition. ( I have considered the pattern to be the one which repeats the most in the given input. )
* Go through the hash array for counts considering modulus to find the non repeated number.

Here is the working code. ( can be improved further. )

void findNonRepeated(char* s ) {
	char a[10];
	char P1 = 0, P2 = 0; 				// pattern 1 and pattern 2
	int P1count = 0, P2count = 0;		// pattern counter
	for ( int i = 0; i < 10; i++ ) a[i] = 0;

	while (*s) {
		a[*s]++;
		s++;
	}

	for ( int i = 0; i < 10; i++ ) {
		if ( a[i] > 1 ) {
			if ( a[i] != P1 && P1 == 0 ) P1 = a[i];

			else if ( a[i] != P2 && P2 == 0 ) P2 = a[i];

			if ( (a[i] % P1) == 0 ) P1count += 1;
			else if ( (a[i] % P2 ) == 0 ) P2count += 1;
		}
	}
 int P;
 P = ( P1count > P2count ) ? P1 : P2; 

 cout << "\nThe non repeated numbers are: " << endl;
 for ( int i = 0; i < 10; i++ ){
	 if ( (a[i] % P) != 0 ) cout << i << ", ";
 }
 cout << "\n";
}

use binary tree to get the numbers arranged and get the count of numbers

#include<iostream>
#include<string>
#include <map>

using namespace std;


//tree node
struct TreeNode{
	int data;
	TreeNode *leftNode;
	TreeNode *rightNode;
	TreeNode(){}
	TreeNode(int data){this->data=data;}
};


//binary tree
class BinaryTree{
	map<int,int> sameNumbers;
	TreeNode* rootNode;
	//create binary tree
	void createTree(TreeNode*& rootNode,int data);
	void showTree(TreeNode*& root);

public:
	BinaryTree(){rootNode=NULL;}

	//starting point for creating tree, root is accessed from this func
	void insert(int data)
	{
		map<int,int>::iterator it;
		it=sameNumbers.find(data);
		if(sameNumbers.size()>0)
		{
			if(it!=sameNumbers.end())
			{
				if(sameNumbers.find(data)->first==data)
				{
					sameNumbers.find(data)->second=sameNumbers.find(data)->second++;
				}
			}
			else
			{
				sameNumbers.insert(pair<int,int>(data,1));
			}
		}
		else
		{
			sameNumbers.insert(pair<int,int>(data,1));
		}

		createTree(rootNode,data);
	}
	//show tree
	void BinaryTree::show()
	{
		showTree(rootNode);
	}

	void showMap();

};

void BinaryTree::createTree(TreeNode*& root,int data)
{
	//check if root is NULL, this is called recursively for left or right side,for every new node
	if(root==NULL)
	{
		root=new TreeNode(data);
		root->leftNode=NULL;
		root->rightNode=NULL;
		return;
	}
	if(root->data<data)
	{

		createTree(root->leftNode,data);
	}
	else
	{
		createTree(root->rightNode,data);
	}
}

void BinaryTree::showTree(TreeNode*& root)
{
	//check if root is NULL, this is called recursively for left or right side,for every new node
	if(root==NULL)
	{
		return;
	}
	showTree(root->leftNode);
	cout<<root->data<<endl;
	showTree(root->rightNode);
}

void BinaryTree::showMap()
{
	cout<<endl;
	int min=sameNumbers.begin()->second;
	int key=sameNumbers.begin()->first;
	for(map<int,int>::iterator it1=sameNumbers.begin();it1!=sameNumbers.end();++it1)
	{
		cout<<it1->first<<" "<<it1->second<<endl;
		int key;
		if(min>it1->second)
		{
			min=it1->second;
			key=it1->first;
		}
	}
	cout<<"number with minmum count"<<min<<" is"<<key;
}




int main()
{
	BinaryTree tree;
	tree.insert(2);
	tree.insert(3);
	tree.insert(4);
	tree.insert(2);
	tree.insert(3);
	tree.insert(3);
	tree.insert(4);
	tree.insert(4);
	tree.show();
	tree.showMap();

	getchar();
	return 0;
}

}

void findIrregularRepeations (int *array)
{
int lastElement = -1;
int repeatCount = 0;
int distinctNos = 0;
int sum = 0;
int *repeatition;
for (int count=0; count<totalSize; count++)
{
if (lastElement == -1)
{
lastElement = array[count];
repeatCount++;
distinctNos++;
}
else
{
if (lastElement == array[count])
{
repeatCount++;
}
else
{
repeatitions = (int*) realloc (sizeof(int) * repeatCount)
repeatition[distinctNos - 1] = repeatCount;
distinctNos++;
lastElement = array[count];
}
}
}

printf("%", FindDuplicates(repeatition, distinctNos));
}

int FindDuplicates(int *repeatition, int distinctNos)
{
for (count=0; count<distinctNos; count++)
dup = dup ^ repeatition[count];
}

Start with the first element. As long as the current element is same as the next element, step ahead two places. When they are different or when only one is left, current one is the first unpaired element.

If the list is sorted or the similar elements are consecutive (1,1,1,5,5,4,7,7,2,2), then its quite easy

int find(int n[], int size)
{
    int i;
    for(i=0; i< size; i++)
    {
        if(n[i] != n[i+1])
        {
            if(n[i+1] != n[i+2])
            {
                if((i+1)< (size -1))
                return n[i+1];
            }
        }
    }
    return -1;
}

If the list is sorted or the similar elements are consecutive (1,1,1,5,5,4,7,7,2,2), then its quite easy

int find(int n[], int size)
{
    int i;
    for(i=0; i< size; i++)
    {
        if(n[i] != n[i+1])
        {
            if(n[i+1] != n[i+2])
            {
                if((i+1)< (size -1))
                return n[i+1];
            }
        }
    }
    return -1;
}

If the list is sorted or the similar elements are consecutive (1,1,1,5,5,4,7,7,2,2), then its quite easy

int find(int n[], int size)
{
    int i;
    for(i=0; i< size; i++)
    {
        if(n[i] != n[i+1])
        {
            if(n[i+1] != n[i+2])
            {
                if((i+1)< (size -1))
                return n[i+1];
            }
        }
    }
    return -1;
}

If the list is sorted or the similar elements are consecutive (1,1,1,5,5,4,7,7,2,2), then its quite easy

int find(int n[], int size)
{
    int i;
    for(i=0; i< size; i++)
    {
        if(n[i] != n[i+1])
        {
            if(n[i+1] != n[i+2])
            {
                if((i+1)< (size -1))
                return n[i+1];
            }
        }
    }
    return -1;
}

If the list is sorted or the similar elements are consecutive (1,1,1,5,5,4,7,7,2,2), then its quite easy

int find(int n[], int size)
{
    int i;
    for(i=0; i< size; i++)
    {
        if(n[i] != n[i+1])
        {
            if(n[i+1] != n[i+2])
            {
                if((i+1)< (size -1))
                return n[i+1];
            }
        }
    }
    return -1;
}

If the list is sorted or the similar elements are consecutive (1,1,1,5,5,4,7,7,2,2), then its quite easy

int find(int n[], int size)
{
    int i;
    for(i=0; i< size; i++)
    {
        if(n[i] != n[i+1])
        {
            if(n[i+1] != n[i+2])
            {
                if((i+1)< (size -1))
                return n[i+1];
            }
        }
    }
    return -1;
}

If the list is sorted or the similar elements are consecutive (1,1,1,5,5,4,7,7,2,2), then its quite easy

int find(int n[], int size)
{
    int i;
    for(i=0; i< size; i++)
    {
        if(n[i] != n[i+1])
        {
            if(n[i+1] != n[i+2])
            {
                if((i+1)< (size -1))
                return n[i+1];
            }
        }
    }
    return -1;
}

If the list is sorted or the similar elements are consecutive (1,1,1,5,5,4,7,7,2,2), then its quite easy

int find(int n[], int size)
{
    int i;
    for(i=0; i< size; i++)
    {
        if(n[i] != n[i+1])
        {
            if(n[i+1] != n[i+2])
            {
                if((i+1)< (size -1))
                return n[i+1];
            }
        }
    }
    return -1;
}

/**
	 * Time: O(N)
	 * Space: O(1)
	 */
	private int firstNotPaired( int[] arr ){
				
		for( int index = 1; index < arr.length; index += 2){
			
			int value1 = arr[index-1];
			int value2 = arr[index];
			
			if( value1 != value2 ){
				
				int count = 1;
				int j = index-2;
				
				while( j >= 0 && arr[j] == value1 ){
					++count;
					--j;
				}
				
				if( count % 2 != 0 ){
					return value1;
				}
				return value2;
			}
		}
		
		// array length is odd
		if( (arr.length & 1) != 0 ){
			return arr[arr.length-1];
		}
		
		// not found
		return 0; 		
	}

Bit XOR

public class findIrregularRepetitions
{
  public static void main(String args[])
  {
    int arr[] = new int[] {2,2,3,3,4,4,6,6};
    int size = 8;
    // System.out.print("0   ");
    int xor = arr[0];
    int sel[] = new int[size];
    int res[] = new int[size];
    int j = 0;
    for (int i = 0; i < size-1; i++)
    {
      // System.out.print (xor + "   ");
      System.out.print ((arr[i] ^ arr[i+1])+ "   ");
      if ((arr[i] ^ arr[i+1]) != 0)
        sel[j++] = i+1;
    }
    System.out.println();
    int lim = j+1;
    sel[j] = size;
    for (j = 0; j < lim; j++)
    {
      if (j == 0)
        res[j] = sel[j];
      else
        res[j] = sel[j] - sel[j-1];
      System.out.print (sel[j] + "   ");
    }
    System.out.println();
    for (j = 0; j < lim; j++)
    {
      // res[j] = sel[j] - sel[j-1];
      System.out.print (res[j] + "   ");
    }
    int ans = -1;
    for (j = 1; j < lim; j++)
    {
      if (res[j] != res[j-1])
      {
        if (res[j+1] != res[j])
        {ans = arr[sel[j]-1]; break;}
        else if (res[j+1] != res[j-1])
        {ans = arr[sel[j-1]-1]; break;}
      }
    }
    System.out.println();
    System.out.println("Ans -> " + ans);
    // System.out.println ( "Ans -> " + firstNotPaired(arr));
  }  
}

Can anyone explain how XOR works. I think it doesn't. Here is my implementation O(n) time complexity and 0(3) space complexity. This program is not very clear because I was handling edge cases as well like if the odd man is in the middle, front, back and doesn't exists. This program is not thread-safe as it is saving data.

public class FirstDifferentRepeatedFormatStupid {
    private int totalCount = 0;
    private HashMap<Integer, Integer> counter = Maps.newLinkedHashMap();

    public static void main(String [] args) {
        List<Integer> integers1 = Lists.newArrayList(1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4);
        List<Integer> integers2 = Lists.newArrayList(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4);
        List<Integer> integers3 = Lists.newArrayList(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4);
        List<Integer> integers4 = Lists.newArrayList(1, 2, 2, 2, 3, 3, 3, 4, 4, 4);
        Integer outLier1 = new FirstDifferentRepeatedFormatStupid().findOutLier(integers1);
        Integer outLier2 = new FirstDifferentRepeatedFormatStupid().findOutLier(integers2);
        Integer outLier3 = new FirstDifferentRepeatedFormatStupid().findOutLier(integers3);
        Integer outLier4 = new FirstDifferentRepeatedFormatStupid().findOutLier(integers4);

        System.out.println(integers1 + "=" + outLier1);
        System.out.println(integers2 + "=" + outLier2);
        System.out.println(integers3 + "=" + outLier3);
        System.out.println(integers4 + "=" + outLier4);
    }
    
    public Integer findOutLier(List<Integer> integers) {
        int firstPointer = 0;
        int secondPointer = 1;
        int size = integers.size();
        int count;
        while (firstPointer < size) {
            count = secondPointer - firstPointer;
            if(secondPointer > integers.size() - 1) {
                Integer isDifferent = isDifferentNumber(count, integers.get(firstPointer), true);
                if(isDifferent != null) {
                    return isDifferent;
                }
                else {
                    return null;
                }
            }
            else if(integers.get(firstPointer).equals(integers.get(secondPointer))) {
                secondPointer ++;
            }
            else {
                Integer isDifferent = isDifferentNumber(count, integers.get(firstPointer), false);
                if(isDifferent != null) {
                    return isDifferent;
                }
                secondPointer = secondPointer + 1;
                firstPointer = secondPointer - 1;
            }
        }
        return null;
    }

    private Integer isDifferentNumber(int count, int number, boolean isEnd) {
        totalCount++;
        if(counter.containsKey(count)) {
            List<Integer> uniqueCounts = Lists.newArrayList(counter.keySet());
            if(counter.size() == 2) {
                if(totalCount >= 3 && uniqueCounts.get(0) == count) {
                    return counter.get(uniqueCounts.get(1));
                }
                else if(totalCount >= 3 && uniqueCounts.get(1) == count) {
                    return counter.get(uniqueCounts.get(0));
                }
            }
        }
        else {
            counter.put(count, number);
        }
        if(isEnd && counter.size() == 2) {
            return number;
        }
        return null;
    }
}

There is no need of hashing or anything. With the use of some variables it can be checked.
Var1:count : for counting number of occurrences of a particular element
Var2:count1: Initial count for first element will be assigned to count1.
Var3: sol1: First element is stored in sol1 var (if the array is{1,222,333,444)
Var4: c1: increase c1 if count == count1

Now just check if count <> count1
if c1<=1 then
element 1 is odd man out
else the current element is odd man out.
break;

Worst case: O(n), depends where the odd man lies


The below is code:

#include <iostream>
using namespace std;

void main(int argc){

int a[17] = {1,1,1,2,2,2,3,3,4,4,4,5,5,5,6,6,6};
int count=1;
int count1=-1;
int c1=0;
int sol1;

for(int i=0; i<17;i++)
{
count=1;
while(a[i] ==a[i+1])
{
count++;
i++;
}
cout<<"count is:"<<count<<endl;
if(count1<0){
count1=count;
sol1=a[i];
}

if(count==count1)
c1++;

if(count1 != count ){
if(c1<=1){
cout<<"Odd man out is: "<<sol1<<" that appears: "<<count1<<" times, where as other element appears: "<<count<<" times"<<endl;
break;
}
else{
cout<<"Odd man out is: "<<a[i]<<" that appears: "<<count<<" times, where as other element appears: "<<count1<<" times"<<endl;
break;

}

}
}
cin.get();
}

Efficiency 0(N). TestCase 1
array = {2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,5,5,5,5,5,5};
array = {2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5};

int maxcount = 0;
int tempcount = 0;

int temp=0;

for(int i=0; i<array.length; i++)
{

{
++tempcount;
if(i+1<array.length){
if(array[i]!=array[i+1])
{
if(tempcount>maxcount)
{
maxcount=tempcount;
temp=i;
}
tempcount=0;
}

}
}


}

if(tempcount>maxcount)
{
maxcount=tempcount;
temp=array.length-1;
}


System.out.println(array[temp]);

garimaa.blogspot.in/2012/04/program-9th-in-c.html

public static void main(String args[]){
int [] arr = new int[]{2,2,3,3,4,4,5,5,5,6,6,7,7};

int l1 = 1, l2 = 0, l3 = 0;
boolean first = false, second=false, done = false;
for (int i = 1; i < arr.length; i++) {
if(arr[i]==arr[i-1] && first==false)
l1++;
else if(arr[i] == arr[i-1] && second==false)
l2++;
else if(arr[i]!=arr[i-1] && first == false && second == false){
first = true;l2++;}
else if (arr[i]!=arr[i-1] && first == true && second == false){
second = true;l3++;}
else if(arr[i] == arr[i-1] && first == true && second == true)
l3++;
else if(arr[i] != arr[i-1] && first == true && second == true){
if(l1 == l2 && l1 == l3 && l2 == l3)
l3=1;
else if(l1 == l2){
System.out.println(arr[i-1]);done = true; break;
}else if(l2 == l3){
System.out.println(arr[0]);done = true; break;
}else if(l1 == l3){
System.out.println(arr[l1]);done = true; break;
}
}
}
if(done==false){
if(l1 == l2)
System.out.println(arr[arr.length-1]);
else if(l2 == l3)
System.out.println(arr[0]);
else if(l1 == l3)
System.out.println(arr[l1]);

}
System.out.println(l1 + " "+ l2 + " "+l3);
}

Assume ints are sorted.

int findNonRepeatedInt(int[] intArray) {
		
		if( intArray == null )
			throw new NullPointerException();
		if( intArray.length == 1 )
			return intArray[0];
		
		int nonRepeatedInt = -1;
		
		try {
			for( int i = 0; i < intArray.length; i += 2 ) {
				if( intArray.length - i == 1 ) {
					return intArray[i];
				}
				if( intArray[i] != intArray[i + 1] ) {
					nonRepeatedInt = intArray[i];
					break;
				}
			}
		} catch( ArrayIndexOutOfBoundsException e ) {
			System.out.println( "out of bound" );
		}
		
		return nonRepeatedInt;
	}

int[] sat1 = {2,2,2,3,3,3,4,4,4,4,4,7,7,7,7,7,7,7,7,7};
int[] sat2 = new int[sat1.length];
int[] sat3 = new int[sat1.length];
int temp = 0;
int num = 0;
for(int i=0;i<sat1.length;i++){
if(temp!=sat1[i]){
temp=sat1[i];
int count = 0;
for(int j=0;j<sat1.length;j++){
if(temp==sat1[j]){
count++;
}
}
sat2[num]=count;
sat3[num]=sat1[i];
// System.out.print(sat2[i] + " ");
// System.out.print(sat3[i] + " ");
System.out.println();
num++;
}
}

for(int k=0;k<sat3.length-1;k++){
// System.out.print(sat2[k] + " ");
if(sat2[k]>sat2[k+1]&&sat2[k]>sat2[k+2]){
System.out.print(sat3[k]+ " ");
break;
}
}

}

Find the mode of the numbers and return the number. to find the mode of the number there are several methods and we can write our own method to find a mode. Its pretty straightforward

import java.util.*;
import java.util.Map.Entry;
public class prog {

public static void main(String[] args) {
int a[]={2,2,3,3,4};

ArrayList al=new ArrayList();

Map<Object,Integer> hm=new HashMap<Object,Integer>();

for (int i = 0; i < a.length; i++) {

al.add(a[i]);
}
for (Object object : al) {
int i=Collections.frequency(al,object);
hm.put(object, i);
}
System.out.println(hm);
ArrayList bl=new ArrayList();
for (Entry<Object, Integer> entry : hm.entrySet()) {

bl.add(entry.getValue());
}

Object o[]=new Object[al.size()];

o=bl.toArray();

Arrays.sort(o);

int fi=0;

for (int i = 0; i < o.length; i++) {

System.out.print(o[i]);
}

if(o[o.length-1]!=o[o.length-2]){

fi=(int)o[o.length-1];
}
else if(o[0]!=o[1]){

fi=(int)o[0];
}
else if(true){

for (int i = 1; i < o.length-1; i++) {

if(o[i]!=o[i-1]&&o[i]!=o[i+1]){

fi=(int)o[i];

}
}
}
for (Entry<Object,Integer> entry : hm.entrySet()) {

if(entry.getValue().equals(fi)){

System.out.println(entry.getKey());
}
}
}
}

You assumed that list is sorted, but lets extend the question for the case that list is not sorted!

Using partitioning would be a potential answer with O(n) and another solution is using Hash Map, count the items in array using item as a key.