Menu
Topics Index
...
`

Weekend Hack - 08 Jun 2013 - Results

Thanks to Pramod Jain, Pramod Kumar Reddy Jella and Gayathri Chandra for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Given the experience of the participants, they were really innovative and clean. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of the Weekend Hack 08 Jun 2013 - 1 is Gayathri Chandra. She will get a recharge or gift voucher worth Rs. 150.

To find the odd man out in multiply and add pair series

Write a program to find the odd man out in multiply and add pair series. Assume that the multipliers and the numbers added are in the range -10 to 10.

Input (int[]) Output (int)
{74, 224, 447, 1345, 2685, 8057, 16113} 1345
{20, 71, 141, 425, 849, 2549} 20
{6, 20, 39, 119, 235, 713, 1425, 4277} 235
{1, 8, 15, 47, 93, 281, 561, 1685} 1
{2, -4, -6, -28, -31, -100, -102, -316} -31
{10, 10, 9, 9, 8, 8, 7, 12, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1} 12
{9, 29, 57, 177, 345, 1037, 2073, 6221} 177
{2, -4, 33, 89, -618, -1865, 13053, 39149} -1865

Solution 1 - Submitted on Sat Jun 1 12:06:43 2013

class OddManOutInMultiplyAndAddPairSeries {

    public static void main(String s[]) {
        int input[] = {6, 20, 39, 119, 235, 713, 1425, 4277};
        System.out.println("The odd man is : " + findOddManOut(input));
    }

    public static int findOddManOut(int[] series) {
        int multiplier1 = 0, multiplier2 = 0, addend1 = 0, addend2 = 0;
        { // new block to limit the scope of boolean variables , numberOfMatches1 ,numberOfMatches2
            boolean flag1 = false, flag2 = false;
            int numberOfMatches1 = 0, numberOfMatches2 = 0;
            outer : for (int multiplier = -10; multiplier <= 10; multiplier++) {
                for (int addend = -10; addend <= 10; addend++) {
                    numberOfMatches1 = 0;
                    numberOfMatches2 = 0;
                    // Loop to find out the multipliers and addends in the given series
                    for (int k = 0; k < series.length - 1; k++) {
                        if (k % 2 == 0 && (series[k] * multiplier + addend) == series[k + 1]) {
                            numberOfMatches1++;
                        } else if (k % 2 == 1 && (series[k] * multiplier + addend) == series[k + 1]) {
                            numberOfMatches2++;
                        }
                    }
                    // Total number of Add multiply relationship with multiplier1 and addend1 = length of series/2 
                    if (numberOfMatches1 >= series.length / 2 - 1) {
                        // If number of matches is greater than or equal to 1 less than existing relations.(expecting one relationship to be odd man out)
                        multiplier1 = multiplier;
                        addend1 = addend;
                        flag1 = true;
                    }
                    // Total number of Add multiply relationship with multiplier2 and addend2 = (length of series-1)/2 
                    if (numberOfMatches2 >= (series.length - 1) / 2 - 1) {
                        // If number of matches is greater than or equal to 1 less than existing relations.(expecting one relationship to be odd man out)
                        multiplier2 = multiplier;
                        addend2 = addend;
                        flag2 = true;
                    }
                    if (flag1 && flag2)
                        break outer; // break outer loop if relationship in series is found
                }
            }
        }
        // checking whether any number violates relationship with its preceding and succeeding number and returning it if any.
        // This loop does not cover first and last numbers of the series
        for (int i = 0; i < series.length - 2; i++) {
            if (i % 2 == 0 && (series[i] * multiplier1 + addend1) != series[i + 1] && (series[i + 1] * multiplier2 + addend2) != series[i + 2]) {
                return series[i + 1];
            }
            if (i % 2 == 1 && (series[i] * multiplier2 + addend2) != series[i + 1] && (series[i + 1] * multiplier1 + addend1) != series[i + 2]) {
                return series[i + 1];
            }
            // both the if's can be merged but keeping them separate for clear understanding.
        }
        // checking if the first number violates the relationship
        if ((series[0] * multiplier1 + addend1) != series[1]) {
            return series[0];
        }
        // checking if the last number violates the relationship
        if ((series.length % 2 == 0 && series[series.length - 2] * multiplier1 + addend1 != series[series.length - 1]) || (series.length % 2 == 1 && series[series.length - 2] * multiplier2 + addend2 != series[series.length - 1]))
            return series[series.length - 1];
        return 0; // if no number is odd man out
    }
}

Review Comments

Overall Rating (out of 10): 7

Solution 2 - Submitted on Sat Jun 1 13:54:04 2013

class OddManOutInMultiplyAndAddPairSeries {

    public static void main(String s[]) {
        int input[] = {6, 20, 39, 119, 235, 713, 1425, 4277};
        System.out.println("The odd man is : " + findOddManOut(input));
    }

    public static int findOddManOut(int[] series) {
        int multiply[] = new int[series.length - 1];
        int add[] = new int[series.length - 1];
        int generateseries[] = new int[series.length];
        int count[] = new int[series.length - 1];
        //multiply and add values of the sequence 
        for (int seriesIterate = 0; seriesIterate < series.length - 1; seriesIterate++) {
            multiply[seriesIterate] = (series[seriesIterate + 1] / series[seriesIterate]);
            add[seriesIterate] = series[seriesIterate + 1] - (multiply[seriesIterate] * series[seriesIterate]);
            //if add value is greater than 10 then check by incrementing multiply value if the value lies b/w -10 and 10 . if not return the value
            if (add[seriesIterate] > 10) {
                if ((add[seriesIterate] - series[seriesIterate] >= -10) && (add[seriesIterate] - series[seriesIterate] <= 10)) {
                    multiply[seriesIterate]++;
                    add[seriesIterate] = add[seriesIterate] - series[seriesIterate];
                } else
                    return series[seriesIterate];
            }
            //if add value is less than 10 then check by decrementing multiply value if the value lies b/w -10 and 10 . if not return the value
            if (add[seriesIterate] < -10) {
                if ((add[seriesIterate] + series[seriesIterate] >= -10) && (add[seriesIterate] + series[seriesIterate] <= 10)) {
                    multiply[seriesIterate]--;
                    add[seriesIterate] = add[seriesIterate] + series[seriesIterate];
                } else
                    return series[seriesIterate + 1];
            }
        }
        //get count of repeated add and multiply values
        count = getCount(multiply, add);
        //most repeated numbers in even positions
        int oddmax = 0;
        int oddpos = 0;
        for (int i = 0; i < add.length; i = i + 2) {
            if (oddmax < count[i]) {
                oddpos = i;
                oddmax = count[i];
            }
        }
        //most repeated numbers in odd positions
        int evenmax = 0;
        int evenpos = 0;
        for (int i = 1; i < add.length; i = i + 2) {
            if (evenmax < count[i]) {
                evenpos = i;
                evenmax = count[i];
            }
        }
        if (evenmax == 1 && oddmax >= (add.length / 2)) {
            for (int z = 0; z < add.length; z = z + 2) {
                if (add[z] != 0)
                    return series[z + 1];
            }
        }
        //if evenmax and oddmax >1 then  add,multiply values at oddpos and evenpos are the alternate multiply and add values in the sequence . 
        if (evenmax > 1 && oddmax > 1) {
            generateseries = generateSeries(series, add, multiply, oddpos, evenpos);
            int difference = compareSeries(series, generateseries);
            if (difference == 1) {
                return oddman(series, generateseries);
            } else if (difference == 0) {
                return 0;
            }
        } else {
            //if evenmax ,and oddmax both are not greater than one .. we need to check by generating sequence for all odd and even posions 
            //generate series for each and every odd and even postions
            for (int i = 0; i < add.length; i = i + 2) {
                oddpos = i;
                if (i + 1 < add.length)
                    evenpos = i + 1;
                else
                    evenpos = i - 1;
                generateseries = generateSeries(series, add, multiply, oddpos, evenpos);
                //number values diffred in series and generated series 
                int difference = compareSeries(series, generateseries);
                // if difference is 1 then there is one odd man otherwise no oddman return 0
                if (difference == 1) {
                    return oddman(series, generateseries);
                } else if (difference == 0) {
                    return 0;
                }
            }
        }
        return 0;
    }

    //finding odd man in series by comparing with generate series
    public static int oddman(int series[], int generateseries[]) {
        for (int k = 0; k < generateseries.length; k++) {
            if (series[k] != generateseries[k])
                return series[k];
        }
        return 0;
    }

    //count no.of values differed in series and generated series
    public static int compareSeries(int series[], int generateseries[]) {
        int count = 0;
        for (int k = 0; k < generateseries.length; k++) {
            if (series[k] != generateseries[k])
                count++;
        }
        return count;
    }

    //code for generating series 
    public static int[] generateSeries(int series[], int add[], int multiply[], int oddpos, int evenpos) {
        int generateseries[] = new int[series.length];
        generateseries[oddpos] = series[oddpos];
        generateseries[evenpos] = series[evenpos];
        int p;
        if (oddpos > evenpos)
            p = evenpos;
        else
            p = oddpos;
        p--;
        while (p >= 0) {
            if (p % 2 == 0)
                generateseries[p] = (generateseries[p + 1] - add[oddpos]) / multiply[oddpos];
            else
                generateseries[p] = (generateseries[p + 1] - add[evenpos]) / multiply[evenpos];
            p = p - 1;
        }
        if (oddpos > evenpos)
            p = evenpos;
        else
            p = oddpos;
        while (++p < series.length) {
            if (p % 2 == 0)
                generateseries[p] = (generateseries[p - 1] * multiply[evenpos]) + add[evenpos];
            else
                generateseries[p] = (generateseries[p - 1] * multiply[oddpos]) + add[oddpos];
        }
        //System.out.println(p);
        return generateseries;
    }

    //code for finding repetetion of the values in multiply and add
    public static int[] getCount(int[] multiply, int[] add) {
        int count[] = new int[add.length];
        for (int i = 0; i < add.length; i++) {
            int c = 0;
            int x = add[i];
            int y = multiply[i];
            //count of repeateation of a numbers in add and multiply
            for (int j = 0; j < add.length; j++) {
                if (add[j] == x && multiply[j] == y)
                    c++;
            }
            count[i] = c;
        }
        return count;
    }
}

Review Comments

Overall Rating (out of 10): 6

Solution 3 - Submitted on Sat Jun 1 14:31:45 2013

class OddManOutInMultiplyAndAddPairSeries {

    public static void main(String s[]) {
        int input[] = {6, 20, 39, 119, 235, 713, 1425, 4277};
        System.out.println("The odd man is : " + findOddManOut(input));
    }

    public static int findOddManOut(int[] series) {
        int i, error = -1, difference[] = new int[series.length - 2];
        boolean check[] = new boolean[series.length - 3];
        //Getting the difference with its succeeding alternate element.
        // the numbers are expected to be in alternate geometric progression
        // (1st number) * a = 2nd number,(2nd number) * b = (3rd number similarly  3rd * a = 4th , 4th * b = 5th and so on..
        for (i = 0; i < difference.length; i++) {
            difference[i] = series[i + 2] - series[i];
        }
        // As the numbers in difference array are in alternate geometric progression two conditions arise
        //if there is a wrong number then there will be deviation from these conditions at few places
        //we will get the set of numbers from the number series which contributed to the value at each of those deviated places
        // intersecting those sets gets the odd man out..
        //condition 1-the number is expected to perfectly divide the next number.
        // if not mark them in some way
        for (i = 0; i < check.length; i++) {
            if ((difference[i + 1] % difference[i]) != 0)
                check[i] = true;
        }
        /* check[i] value depends on difference[i] value and difference[i+1] value where difference[i] depends on series[i] and series[i+2], and difference[i+1] depends on series[i+1] and series[i+3] values.*/
        // if there is deviation from the condition at position i in the above matrix i.e, check[i] is true then wrong number may be at position i or i+1 or i+2 or i+3 in the number series.
        // condition 2 is- alternate numbers are expected to be in GP with a*b as geometric mean
        // get the final position where this relationship is not followed
        for (i = check.length - 2; i >= 0; i--) {
            if ((difference[i + 2] % difference[i]) != 0) {
                error = i;
                break;
            }
        }
        // If we get error at i in this for loop then wrong number may be at position i or i+2 or i+4 in series 
        // cuz difference[i] depends on series[i] and series[i+2], and difference[i+2] depends on series[i+2] and series[i+4]
        // By analysing the sets of numbers which contributed to the values at the places where any of the two conditions are not met, we can get the wrong number i.e, odd man out
        // for example consider error=i= 3 then we will verify check[3(i)] and check[4(i+1)].suppose check[3]=true and check[4]=false.
        // Error=3(i) implies wrong number is at either of 3(i) or 5(i+2) or 7(i+4) positions.........(1)
        // Check[3(i)]=true implies wrong number is at either of 3(i),4(i+1),5(i+2),6(i+3) positions .........(2)
        // Check[4(i+1)]=false implies numbers at 4(i+1),5(i+2),6(i+3),7(i+4) positions are correct..........(3)
        /* from (1) and (2) we get wrong number is at either position 3(i) or 5(i+2), but from (3) we get 5(i+2) is a correct number which implies wrong number is at position 3(i).*/
        //similarly if error=3 ,check[3]=true and check[4]=true then odd man is at position 5(i+2) 
        // if error=3, check[3]=false and check[4]=true then odd man is at position 7(i+2)
        if (error != -1) {
            if (check[error])
                if (check[error + 1])
                    return series[error + 2];
                else
                    return series[error];
            else
                return series[error + 4];
        }
        return 0; // if no odd man out
    }
}

Review Comments

Overall Rating (out of 10): 8

© meritcampus 2019

All Rights Reserved.

Open In App