info@meritcampus.com    +91-85006-22255
...
`

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

Overall Rating (out of 10): `7`

• The code is easy to follow and the comments are useful.
• Effective use of label to break out of the outer loop.
• There is duplicate code while checking with the number in the next series. Could have created a method to remove this duplicate code.

• Better variable names could be given to flag1, flag2

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

Overall Rating (out of 10): `6`

• The code is easy to follow and the comments are useful.
• Although methods are effectively used to reduce the duplicate code, we could further reduce the number of lines by improving the algorithm.
• Naming conventions for variables and methods are properly followed.

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

Overall Rating (out of 10): `8`
• Although not necessary, it is better to enclose the `if` and `else` bodies in flower braces, even if only one statement is present.