CODEWITHSUNDEEP
c++
bdon
bdon

Reputation: 1

Tips on Improving Efficiency of this Code (Beginner)

I am currently doing a coding exercise and am missing some cases due to the time limit being exceeded. Can I get some tips on how to improve the efficiency of my code? Also if you have any general tips for a beginner I would also appreciate that. The problem is below and thanks.

You are given all numbers between 1,2,…,n except one. Your task is to find the missing number.

Input

The first input line contains an integer n.

The second line contains n−1 numbers. Each number is distinct and between 1 and n (inclusive).

Output

Print the missing number.

Constraints 2≤n≤2⋅105 Example

Input:

5
2 3 1 5

Output:

4

Here is my code:

#include <bits/stdc++.h>

using namespace std;

int missingNumber(vector<int> available, int N) {
    for (int i=1; i<=N; i++) {
        bool counter = false;
        for (int j=0; j<N-1; j++) {
            if (i == available[j]) {
                counter = true;    
            }
        }
        if (counter == false) {
            return i;    
        }
    }    
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    vector<int> available(N-1);
    int temp = 0;
    for (int i=0; i<N-1; i++) {
        cin >> temp;
        available[i] = temp;
    }
    cout << missingNumber(available, N);
}

Upvotes: 0

Views: 84

Answers (2)

yaodav
yaodav

Reputation: 1256

here is an answer with two versions to your problem

the first version is using Arithmetic progression formula n*(a1 + an) /2 and then subtract your vector sum with the result of the formula.

double missingNumber_ver1(std::vector<int> available, int N) {
    // formula for sum for Arithmetic progression
    double sum = N * (available[0]+available[N-2]) /2;
    double available_sym = std::accumulate(available.begin(), available.end(), 0); // this is to sum the giving numbers
    double missing_num = sum-available_sym;
    return missing_num;
}

the second version is to use XOR operator and when there is a xor value that is not 0 that means this is the missing number. I'm also using std::iota to build the comparison vector with range values.

double missingNumber_ver2(std::vector<int> available, int N) {
      std::vector<int>tem_vec(N-1);  
      std::iota(tem_vec.begin(), tem_vec.end(), available[0]);
      auto av_it = available.begin();
      auto tem_vec_it = tem_vec.begin();
      while(!(*av_it ^ *tem_vec_it))
      {
        av_it++;
        tem_vec_it++;
      }
      return *tem_vec_it;
    }

and here is the full code - look that I made few changes also in the main() function

 #include <iostream>
 #include <numeric>
 #include <vector>

double missingNumber_ver1(std::vector<int> available, int N) {
    // formula for sum for Arithmetic progression
    double sum = N * (available[0]+available[N-2]) /2;
    double available_sym = std::accumulate(available.begin(), available.end(), 0);
    double missing_num = sum-available_sym;
    return missing_num;
}

double missingNumber_ver2(std::vector<int> available, int N) {
  std::vector<int>tem_vec(4);
  std::iota(tem_vec.begin(), tem_vec.end(), available[0]);
  auto av_it = available.begin();
  auto tem_vec_it = tem_vec.begin();
  while(!(*av_it ^ *tem_vec_it))
  {
    av_it++;
    tem_vec_it++;
  }
  return *tem_vec_it;
}


int main() {
    int N;
    std::cin >> N;
    std::vector<int> available;
    int temp = 0;
    for (int i=0; i<N-1; i++) {
        std::cin >> temp;
        available.push_back(temp);
    }
    std::cout << "missingNumber_ver1 " << missingNumber_ver1(available, N) << "\n";
    std::cout << "missingNumber_ver2 " <<missingNumber_ver2(available, N) << "\n";
}

Upvotes: 1

JManirouc
JManirouc

Reputation: 21

A very simple solution with O(N) complexity is based on the observation that if the N-1 numbers are all between 1 and N and distinct from each other, then it suffices to:

  1. compute the sum of all these N-1 numbers, so linear complexity
  2. subtract the sum computed at step 1 from the sum of the N numbers from 1 to N, which we know is N * (N + 1) / 2, so O(1) complexity.

Upvotes: 2

Related Questions