Checking whether odd or even number was inserted into an array without storing user input values

[blizzardd]

Hello. I'm new to C++ and I have a task for my homework to check whether odd or even number was added to an array. All the numbers in it are the same (even or odd) except one which I have to find. The size of an array is big (10^12) so the code runs into time limit exceeded error while checking all the numbers. I have this code below that I wrote by myself, but the only suggestion I received for fixing this issue was avoid storing all the user input values. I have no idea how to do that, so maybe anyone could help me with this?

 #include <iostream>
using namespace std;
void funk(long long a[],long long n,long long &lyg,long long &nelyg);
long long a[10000000];
int main()
{
    long long n,lyg=0,nelyg=0;
    cin>>n;
    for (long long i = 0; i < n; i++) {
        cin >> a[i];
    }
funk(a,n,lyg,nelyg);
if(lyg>nelyg)
{
  cout<<"NELYGINIS";
}
else
{
  cout<<"LYGINIS";
}

}

void funk(long long a[],long long n,long long &lyg,long long &nelyg) {
  for(long long i=0;i<n;i++){
    if(a[i]%2==0)
    {
      lyg++;
    }
    else
    {
      nelyg++;
    }
  }
}

[ne555]

> The size of an array is big (10^12)
> long long a[10000000];
I want to store the sea and you give me a bucket.

> All the numbers in it are the same (even or odd) except one which I have to find
¿what do you need to find? ¿the actual value or only if it is even or odd?

[dhayden]

I have a task for my homework to check whether odd or even number was added to an array.

Ah, but you don't. There's no requirement that the numbers be added to an array. You just have to read the numbers and find the one that's different.

All the numbers in it are the same (even or odd) except one which I have to find.

This would be easy if you knew which type of number (even or odd) you were looking for.

So how many numbers do you need to examine to figure that out?

Figure out if you're looking for an odd number or an even one. Then when you find it, you're done - no need to read the remaining numbers.

Make sure you deal with the special cases when the number you're looking for appears while you're trying to determine which type you're looking for.

[George P]

An array of 10 million elements, stored on the stack. *OUCH* Crash and burn time!

An array of 10 million elements, stored on the heap (free store). That is better.

Frankensteined code below, is there a better way to check for odd or even in 3 array elements no matter where the odd/even number is located?

#include <iostream>

int main()
{
   enum EvenOdd { Even = 0, Odd = 1 };

   const int num { 10'000'000 };

   int* num_arr = new int[num];

   for (size_t i { }; i < num; i++) { num_arr[i] = Odd; }

   num_arr[427] = Even;

   EvenOdd toFind { };

   if (num_arr[0] == num_arr[1] && num_arr[1] == num_arr[2] && num_arr[2] == num_arr[0])
   {
      (num_arr[0] % 2) ? toFind = Even : toFind = Odd;
   }
   else if (num_arr[1] == num_arr[2])
   {
      (num_arr[0] % 2) ? toFind = Even : toFind = Odd;
   }
   else if (num_arr[0] == num_arr[2])
   {
      (num_arr[1] % 2) ? toFind = Even : toFind = Odd;
   }
   else
   {
      (num_arr[2] % 2) ? toFind = Even : toFind = Odd;
   }

   for (size_t i { }; i < num; i++)
   {
      if ((num_arr[i] % 2) == toFind)
      {
         std::cout << (toFind ? "Odd" : "Even") << " number found at: " << i << '\n';
         break;
      }
   }

   delete[] num_arr;
}

Even number found at: 427

[jonnin]

Hmm. what school has TLE on homework problems?! Codechef U?

% is probably more cpu clocks than == or &1
unclear, are all the values the *same* except 1, or are they all the same even/odd except 1?
regardless all you need is
get first value. get some info from it based off actual problem (odd/even or just its value, depending?)
do
get input
while(input vs firstinput condition not matched)
and its done. you have found it. no array/storage .

[ne555]

> An array of 10 million elements
no, 10^12

> is there a better way to check for odd or even in 3 array elements
from the op

funk(a, 3, even, odd);
if(even < odd)

[George P]

no, 10^12

long long a[10000000];
1 one, 7 zeroes. 8 total digits.

10^7, not 10^12.

That is why I wrote it as const int num { 10'000'000 };

The OP mentioned 10^12 as the size of the array, then used 10^7 to initialize the array in code.

Nevertheless it is still a big number for trying to create an array on the stack.

[keskiverto]

jonnin wrote:

Hmm. what school has TLE on homework problems?! Codechef U?

Codechef UCompetetive students would not post (anyw)here, for they want to show their true skill fair and square ...