-2

Well I don't intend to use any data structures here because I don't have any knowledge about them. So I am using only arrays...In this approach the time complexity is reduced to O(n), and the algorithm is similar to hashing...sort of...So the problem is simple, its not running. It is just not running at all in my VS code. I also tried in online C++ compilers, there the output is coming 1 for every input I give. What is happening ?

#include <iostream>
#include <climits>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int array[n];
    for(int i=0;i<n;i++){
        cin>>array[i];
    }
    
    
    
    const int N=1e6+2;
    int idx[N];
    for(int i=0;i<N;i++){
        idx[i]=-1;
    }
    
    
    int min_index=INT_MAX;
    for(int i=0;i<n;i++){
        if(idx[array[i]]==-1){
            idx[array[i]]=i;
        }
        else{
            min_index=min(min_index,idx[array[i]]);
        }
    }
    cout<<min_index<<endl;
    return 0;
}
Shay
  • 23
  • 3
  • Just count your values and break when you count a value a second time. – sweenish Jan 16 '22 at 08:06
  • Just compare the current item with the next one and if the same return the index – Ian4264 Jan 16 '22 at 08:10
  • On a side note - `int array[n];` is [not standard C++](https://stackoverflow.com/questions/1887097/) when `n` is not a compile time constant. – Remy Lebeau Jan 16 '22 at 08:10
  • The array is not sorted so we can't just compare the current with next element – Shay Jan 16 '22 at 08:16
  • What does its not running mean? Are you in difficulties to compile and run it? – Öö Tiib Jan 16 '22 at 08:18
  • Another note - `const int N=1e6+2; int idx[N];` is allocating 3.8MB on the local stack of the main thread. That is likely to cause a stack overflow at runtime, as a thread's stack size is typically much smaller than that. Even if it doesn't, `idx[]` doesn't have enough slots to cover every possible `int` value the user may enter into the `array[]` – Remy Lebeau Jan 16 '22 at 08:18
  • @Shay Look at [std::adjacent_find](https://en.cppreference.com/w/cpp/algorithm/adjacent_find). Note -- *Searches the range [first, last) for two consecutive equal elements.* -- That and `std::distance` makes this a 2 line solution, without loops. Also: `int array[n];` --> `std::vector array(n);` – PaulMcKenzie Jan 16 '22 at 08:27

1 Answers1

0
#include <iostream>
#include <climits>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int array[n];
    for(int i=0;i<n;i++){
        cin>>array[i];
    }
    
    
    
    const int N=1e6+2;
    int idx[N];
    for(int i=0;i<N;i++){
        idx[i]=-1;
    }
    
    
    int min_index=INT_MAX;
    for(int i=0;i<n;i++){
        if(idx[array[i]]==-1){
            idx[array[i]]++;
        }
        else{
            cout << i<<endl;
            break;
        }
    }
    return 0;
}

Although this is not the best approach to doing this because there is wastage of memory instead of array of size N you can use unordered_map or set

Shyamji Tiwari
  • 21
  • 8