Missing Term Arithmetic Progression - Clean up my code

Question

I just tried a little online programming quiz that asked me to solve this problem as quickly as possible. I got the right answer but I know it isn't pretty. I'm trying to become a better programmer and write cleaner, more efficient code so please give me some tips. I've included the description below. PS I think this algorithm fails for the case N=3

# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys
N= int(sys.stdin.readline())
stringdata =  sys.stdin.readline()
array = stringdata.split(' ')
diff1=[0]*(N-1)
diff2 = [0]*(N-2)
index = 0
diff = 0
for i in  range(0,len(array)-1):
    first_diff[i] = int(array[i+1])-int(array[i])
for i in   range(0,len(diff1)-1):
    second_diff[i] = first_diff[i+1]-first_diff[i]
    if second_diff[i] == 0:
        diff = first_diff[i]
    else:
        index = i
print(int(array[index])+diff)

Task: Find the missing term in an Arithmetic Progression.

An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. You are provided with consecutive elements of an Arithmetic Progression. There is however one hitch: Exactly one term from the original series is missing from the set of numbers which have been given to you. The rest of the given series is the same as the original AP. Find the missing term.

Input Format The first line contains an Integer N, which is the number of terms which will be provided as input. This is followed by N consecutive Integers, with a space between each pair of integers. All of these are on one line, and they are in AP (other than the point where an integer is missing).

Output Format One Number which is the missing integer from the series.

Sample Input 5 1 3 5 9 11

Sample Output 7

Answer 1

Here is my code, work for both positive difference and negative difference...

def find_arith(aplist):
   idiff=[]
   flag=0
   for j in range(0, len(aplist)-1):
      diff1 = aplist[j+1] - aplist[j]
      if diff1 < 0:
         flag=1
      idiff.append(abs(diff1))
   if flag==1:
     final_diff=-1*min(idiff)
   else:
     final_diff=min(idiff)
   print(idiff)
   print("final diff:", final_diff)
   for i in range(aplist[0],aplist[len(aplist)-1]+1,final_diff):
      if i not in aplist:
         print(i)

if __name__ == "__main__":

   print("First Result")
   find_arith([13,21,25,33,37,45])
   print("Second Result")
   find_arith([-10,-6,-4,-2])
   print("3rd Result")
   find_arith([-5, -1, 3, 11])
   print("4th Result")
   find_arith([1, 5, 13, 17, 21])

   print("5th Result")
   find_arith([-2, -8, -11, -14, -17, -20, -23, -29])

Answer 2

N = input()
max_num = range(N)
s = raw_input()
AP = map(int,s.split())
comm_dif = AP[1]-AP[0]
length = len(AP)
for i in range(N):
    if i != length-1:
        if AP[i+1]-AP[i] != comm_dif:
            print AP[i]+comm_dif

INPUT:

 5
 1 21 31 51 61

OUTPUT:

 41

Answer 3

Works for

1) Any value of N (given 5 in example)

2) Any Difference between terms (given 2 in example)

3) Difference can be + as well as - (example: 11 5 2 -1 -4)

int diff[]= new int[length-1];
for(int i = 0; i<length-1;i++){
    diff[i] = n1[i+1]-n1[i];
    //System.out.println(diff[i]);
    if(i!=0){
        if(diff[i]<diff[i-1]){
            if(diff[i]<0)
                System.out.println(n1[i]+diff[i-1]);
            else
                System.out.println(n1[i-1]+diff[i]);
            break;
        }
        if(diff[i]>diff[i-1]){
            if(diff[i]<0)
                System.out.println(n1[i-1]+diff[i]);
            else
                System.out.println(n1[i]+diff[i-1]);
            break;
        }
    }
}

n1 is where you store the number array from String.

Length is how many numbers you are providing.

This is optimized so that if you miss number in between first two numbers then it only loops 3 times no matter how many numbers you have given

Answer 4

2 For Loops for a simple problems such as this !! that solution above is Quadratic in its behavior !!

Here is one solution which is O(N) for the worst case behavior where the item @ index 1 is missing and for any item missing after index 1 the solution is better than linear.

The Arithmetic Progression(input Array) to this method, Substitute the SYSOUT with returns appropriately.

solution:

 public static int findMissingNumberInAP(int[] ipArr)
{
    // ipArr will always be more than 3 elements in size.
    int maxDiff = ipArr[1] - ipArr[0];
    int i=0;
    while(i<ipArr.length-1)
    {
        if((ipArr[i+1] - ipArr[i]) > maxDiff)
        break;
        i++;
    }
    // This means the 2nd element or i=1 was missing so add ip[0] to
    // any random difference you are good to go.
    if(i == ipArr.length - 1) 
    System.out.println(ipArr[0] + (ipArr[ipArr.length-1]-ipArr[ipArr.length-2]));
    else System.out.println(ipArr[i] + maxDiff);
    // Else just add the maxDiff you got from first step to the position 
    // of i you broke the loop at.
    return -1;
}

Answer 5

int a[]={1,3,5,7,11};
int i=0,n=5,fd,sd;
printf("output:\n");
do
{
    fd=0;sd=0;
    fd=a[i+1]-a[i];
    sd=a[i+2]-a[i+1];
    if(fd<sd)
    {
        printf("missing term is %d",fd+a[i+1]);
    }
    else if(fd>sd){
       printf("missing term is %d",a[i]+sd);}
    else{
       i++;}
}while((fd==sd)&&i<n-2);

Answer 6

Its very simple , review the code below and if you removed the blank lines it will be exactly 8 lines I hope this answer is clear for you

import re
N = int(raw_input())        #Number of Terms
I = raw_input()             #The Series of Numbers received as a String

I =  re.findall(r'\d+',I)   #Extract items from the string 

I = [int(s) for s in I]     #I is a list with Series of Integers

for x in range(N-1):

    if (I[x]+2 != I[x+1]):
    print I[x]+2

Answer 7

I think this code can be somewhat simplified. First, the input. Not much different, except I use raw_input (or input in Python 3), and I immediately map the numbers to int.

n = int(raw_input("Number of Numbers: "))
s = raw_input("List of Numbers, space-separated: ")
nums = map(int, s.split())
assert n == len(nums) and n > 2

Now for the interesting part: Note that (assuming the list is well-formed) there can just be two differences between numbers: Either the correct difference, or two times that difference. I use a list comprehension to create a list of tuples (difference, at index). Now I can simply use the builtin max function to find the one with two times the correct difference and the respective index (d2, index) and calculate the missing number.

diffs = [(nums[i+1] - nums[i], i) for i in range(n-1)]
(d2, index) = max(diffs)
print nums[index] + d2 / 2

But the question was about coding style, not about the algorithm, so here are my thoughts:

• add some blank lines and comments between logical blocks of your program (e.g. # read input)
• map the array to int once, instead of casting the numbers each time you need them
• you can use a list comprehension to create diff1 (aka first_diff), as in my example
• you don't need diff2 at all; just write if diff1[i+1] - diff1[i] == 0:
• be concise: range(0,len(array)-1) is the same as range(N-1)