Geek Answers Handbook

Find the missing number from the given arithmetic progression

I ran into this problem when you were assigned a number Nas Input, and then N numbers followed (where 3 <= N <= 2500). These numbers Nwere part of the arithmetic progression (size N+1) from which one number was removed. Therefore, the task was to find this missing number. For example,

5
1 3 5 9 11

Output signal 7

I came up with two methods, the second - all test cases, but the first one does not work in certain (hidden) cases.

I will explain the second method first

METHOD II

Let diff=(last_number-first_number)/N
 //Considering 0 based indexing
 for i=0 to (N-2)
    if( array[i+1] is not equal to (array[i]+diff))
          print (array[i]+diff)
          break

This method has passed all test cases. Now, the first method that I performed, and which failed some test cases, was as follows:

METHOD I

 //Considering 0 based indexing
 for i=1 to (N-2)
      if (2*array[i] is not equal to (array[i-1]+array[i+1])) then
              if( (array[i]-array[i-1])< (array[i+1]-array[i]))
                      print 2*array[i]-array[i-1]
              else 
                      print 2*array[i]-array[i+1]
              break

- , METHOD I? . .

+4
5

1 , .

7 5 1 3, 9.

2 , , .

+7

, O (logN) ( ). .

  if(a[mid] != mid*(difference)+a[0]) {

        missing_num = mid*(difference) + a[0];
        search lower half
  }

  else search higher half
+3

Ruby:

number_of_terms = gets.chomp.to_i

STDIN

progression = gets.chomp.split(' ').map(&:to_i)

, , .

expected_sum = (number_of_terms+1)/2.0*(progression.first+progression.last)

: n/2 (a [0] + a [n]).

2,0. .

actual_sum = progression.inject(:+)

, .

missing_element = (expected_sum - actual_sum).to_i

- , , . .0

. 4.0 = > 4

puts "Missing element is: #{missing_element}"
+2

1) N ( 5)

2) ( 2)

3) +, - (: 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 - String.

- , .

This is optimized in such a way that if you skip a number between the first two numbers, it will be only three times, regardless of how many digits you specify

+1
source 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int findDelta(long *x, int n);

int main(){
    int n;
        fscanf(stdin,"%d",&n); 
        long *x= (long*) calloc(n,sizeof(long));
    long k;
    for(int i=0;i<n;i++){
        scanf("%ld",&k);
        x[i]=k;
    }

    int delta=findDelta(x,n);
    for(int i=0;i<n-1;i++){
        if (x[i+1]-x[i] != delta)
            printf("%ld\n",x[i]+delta);
    }
    free(x);    
    return 0;
}

int findDelta(long *x, int n){
    long delta1,delta2;
    delta1=x[1]-x[0];
    int d1Count=0;
    int d2Count=0;

    for(int i=1;i<n-1;i++){
        delta2=x[i+1]-x[i];
        if(delta2==delta1)
          d1Count++;
        else
          d2Count++;
    }
    if (d1Count > d2Count)
        return (delta1);
    else
        return (delta2);
}
+1
source

More articles:


All Articles