CareerCup

Please can you explain the concept behind your code?

Void DiffPiar( int array , int array_size){
map<int , int> store //cretae a map to store resulte
int temp;
for ( i=array_size -1 ; i>= 0 ; i-- ){
for( j=0; j<i ; j++{
temp=Difference ( array[0] , array [ j+ 1 ] )
array[j]=temp;
ii=search the map to see whether this temp element is already present inside the map or not , if present return the map index.
if it's present then just increment it's no of occur enc , ie second field in my code.
else
insert this temp element inside the map and keep second element 1.
}
}

after completing this search the map-second elements which are divisible by 2 , and prints those data ..

Example:
array : 1 2 3 6
pass1: 1 2 5
pass 2: 1 4
pass 3: 3

map contains
1->;2
2->;1
3->;1
4->;1
5->;1

c++ solution of this problem
 /*
 Given a sorted array. Find the number of couples with the same difference. For example we can have an array with 2 couples whose difference is 3 and 4 couples whose difference is 5. The Output should be 2 & 4.
 developed by : Suman Roy
Email        : email.suman.roy@gmail.com
 */
#include<iostream>
#include<stdlib.h>
#include<fstream>
#include<map>
using namespace std;
int Diff( int &num1 , int &num2 ){
	if ( num1 > num2 ) return num1-num2;
	else return num2-num1;
}
typedef std::map< int , int > storage;
void Print ( storage store ){
	std::cout<<"pair output-->\n";
	for( storage::iterator ii=store.begin() ; ii!=store.end() ; ii++ ){
	        int temp=ii->second;
		 if ( temp % 2 == 0 )
		       std::cout<<ii->first<<" == "<<ii->second <<std::endl;
	}
}

void DiffPair(int *i_array , int &i_num ){
	storage store;
	storage::iterator ii;
	int temp;
	for ( int i=i_num-1 ; i>=0 ; i-- ){
		for( int j=0 ;j<i ; j++ ){
			temp=Diff ( * i_array , * ( i_array + j + 1 ) );
			* ( i_array + j ) = temp;
			ii=store.find ( temp );

			if ( ii== store.end() )
				store[ temp ] =1;
				
			else
				ii->second++;
			
		}
	}
	Print ( store ) ;
}

int main(){
	int i_size;
	std::cin>>i_size;
	int *i_array=new int [ i_size ];
	int i_value;
	for ( int i=0 ; i<i_size ; i++ )
		std::cin>> * ( i_array + i );
	std::cout<<"Print sorted array\n";
	for( int i=0 ; i<i_size ; i++ )
		std::cout<<* ( i_array + i )<<" ";
	std::cout<<std::endl;
	DiffPair( i_array , i_size );

}

Is duplicated counted? For eg: If array has four elements say 2,2,3,3 then I have 2 couples with difference 1 or only one couple?

An approach of binary search is considered although it takes O(nlogn) time in the end because of sorting.First store all possible set of differences in the array and then sort it and check for pairs Here is the code you can test it and ask for any queries:

#include <stdio.h>
#include <conio.h>

int compare(const void *a,const void *b)
{
    return ((*(int *)a)-(*(int *)b));
}
void findCouple(int arr[],int arr1[],int *i,int low,int high)
{
    if(low==high)
    {
        return;
    }
    else if(low+1==high)
    {
        arr1[*i]=arr[high]-arr[low];
        *i=*i+1;
        return;
    }
    else
    {
        int mid=low+(high-low)/2;
        if(low+2==high)
        {
        arr1[*i]=arr[mid]-arr[mid-1];*i=*i+1;
        arr1[*i]=arr[mid+1]-arr[mid];*i=*i+1;
        arr1[*i]=arr[mid+1]-arr[mid-1];*i=*i+1;
        return;
       }
       else if(low+3==high)
      {
          arr1[*i]=arr[mid]-arr[mid-1];*i=*i+1;
         arr1[*i]=arr[mid+1]-arr[mid];*i=*i+1;
         arr1[*i]=arr[mid+1]-arr[mid-1];*i=*i+1;
         arr1[*i]=arr[high]-arr[mid-1];*i=*i+1;
         arr1[*i]=arr[high]-arr[mid];*i=*i+1;
         return;
       }
       else
       { 
            arr1[*i]=arr[mid]-arr[mid-1];*i=*i+1;
         arr1[*i]=arr[mid+1]-arr[mid];*i=*i+1;
         arr1[*i]=arr[mid+1]-arr[mid-1];*i=*i+1;
         arr1[*i]=arr[high]-arr[mid-1];*i=*i+1;
         arr1[*i]=arr[high]-arr[mid];*i=*i+1;
         arr1[*i]=arr[mid]-arr[low];*i=*i+1;
       }
        findCouple(arr,arr1,i,low,mid-1);
        findCouple(arr,arr1,i,mid+1,high);
        return;
    }
}
int main()
{
    int arr[]={1,5,8,11,14,17,20,23,27};
    int arr1[30];
    int i=0;
    int n=sizeof(arr)/sizeof(arr[0]);
    findCouple(arr,arr1,&i,0,n-1);
    int j,count1=0,count2=0,diff1=0,diff2=0;
    qsort(arr1,n+2,sizeof(int),compare);
    for(j=0;j<i;)
    {
        if(arr1[j]==arr1[j+1])
        {
            count1++;
            if(count1==2)
            {
                diff1=arr1[j];
            }
            count2++;
            if(count2==4)
            {

                diff2=arr1[j];
            }
            j=j+2;
        }
        else
        {
            j=j+1;
        }
    }
    if(diff1==diff2)
        printf(" The 4 couples occur with difference of %d ",diff1);
    else if(diff1!=diff2&&(diff1!=0&&diff2!=0))
    {
        printf(" The two couples are there with difference of %d and 4 couples with %d",diff1,diff2);
    }
    else if(diff1!=0&&diff2==0)
    {
        printf(" The 2 couples with difference is %d ",diff1);
    }
    else if(diff2!=0&&diff1==0)
    {
        printf(" The 4 couples with difference is %d ",diff1);
    }
}

sites.google.com/site/spaceofjameschen/annnocements/findthenumberofcoupleswiththesamedifference

void PrintPairCount(int* arr, int len)
{
    hash_map<int, int> hm;

    for(int i = 1; i < len; ++i){
        for(int j = 0; j < i; ++j){
            int d = arr[i] - arr[j];
            auto it = hm.find(d);

            if(it == hm.end()){
                hm.insert(pair<int, int>(d, 1));
            }
            else{
                it->second ++;
            }
        }
    }
    cout << "The output is " << endl;
    int count(0);
    for(auto it = hm.begin(); it != hm.end(); ++it){
        if(it->second != 1){
            cout << "Find " << it->second << " pairs with difference of ";
            cout << it->first << endl;
            count ++;
        }
    }

    if(count == 0){
        cout << "No pair shares the same difference" << endl;
    }
}

ii=store.find ( temp );

if ( ii== store.end() )
store[ temp ] =1;

else
ii->second++;


can anybody tell me ..what does this code mean?

/**
 * More more solutions visit blog.abhinavmathur.net
 * 
 *
 */
public class FindSameDifferenceCouple {

    public static void main(String[] args) {

        int[] arr = new int[4];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
             
        // this is the max difference which can exists between two elements as
        // array is sorted
        int maxDiff = arr[arr.length - 1] - arr[0];
        
        // to make more efficient , we could have used a hashmap instead of array
        int[] numCop = new int[maxDiff];
        
        
        // loop over all possible differences betweene elements,
        // we just leave 0 difference couples.
        for(int j=0;j<maxDiff;j++) {
            numCop[j] =0;
            for(int i=0;i<arr.length;i++) {
               int findElem = arr[i]+j;
               if(find(findElem,arr,i)) {
                   numCop[j] = numCop[j]+1;
               }
           }
        }
        
        for(int j=0;j<numCop.length;j++) {
            System.out.println(j+"\t"+numCop[j]);
        }
    }

    // we can make this more efficient by doing a binary search
    private static boolean find(int findElem, int[] arr, int i) {
        for(int j=i+1;j<arr.length;j++)
        {
            if(arr[j] == findElem)
                return true;
        }
        return false;
    }
}

import java.util.HashMap;
import java.util.Map;

public class TestArrayDifference {
int arr[];
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
int diff=0;
public static void main(String[] args) {

TestArrayDifference testArrayDifference=new TestArrayDifference();
testArrayDifference.setArray(5);
testArrayDifference.findDifference();
System.out.println(testArrayDifference.arr);
}
private void setArray(int x) {
arr=new int[x];
for(int i=0;i<x;i++){
arr[i]=i+i*2+(i/2*i); //any dummy number in sorted order
System.out.println(arr[i]);
}
}
private void findDifference(){
for(int i=0;i<arr.length;i++){
for(int j=1;j<arr.length-i;j++){
diff=arr[j]-arr[j-1];
int x=0;
if(map.get(diff)!=null){
map.put(diff, map.get(diff)+1);
}else{
map.put(diff,1);
}
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println("diffrence = " + entry.getKey() + ", No of couples = " + entry.getValue());
}
}
}
}

Here's a C# solution. Worst case time complexity of this algorithm is O(n!/2(n-2)!) or O(n choose 2), if I'm not mistaken. Every element in the input is compared with every other element in unique combinations.

public int[] NumCouplesSameDifference(int[] values) {
	Dictionary<int, int> differences = new Dictionary<int, int>();
	if(values == null || values.Length < 2) return new int[0];
	for (int i = 0; i < values.Length - 1; ++ i) {
		for (int j = i + 1; j < values.Length; ++j) {
			int difference = values[j] - values[i];
			if (!differences.ContainsKey(difference)) {
				differences.Add(difference, 0);
			}
			differences[difference]++;
		}
	}
	
	List<int> results = new List<int>();
	foreach (int key in differences.Keys) {
		if(differences[key] > 1) {
			results.Add(differences[key]);
		}
	}
	
	return results.ToArray();
}