1

I took a coding sample test and I think it's really easy. They ask to find if a number appears in the array (print out YES) or not (print out NO). At first, I want come up with binary search method. But when I see their given function, I think it's not suitable to use that method.

In the description, they mention arr[] and k as the number we need to check if k appears in arr[]. 

char* findNumber(int arr_count, int arr[], int k)
{
 int n = sizeof(arr)/sizeof(arr[0]);
  for(arr_count = 0; arr_count < n; arr_count++)
  {
     if(arr[arr_count]==k)
       cout<<"YES";
     else
       cout<<"NO";
  }
  return 0;
}

But when I compiled, it showed the output is null. I don't know why? I solved many more difficult problems. So I feel so bad when I got error in an easy task like this. Please tell me the wrong part.

Retired Ninja
  • 4,785
  • 3
  • 25
  • 35
Hector Ta
  • 81
  • 2
  • 14
  • Consider what you print if the first item in the array doesn't match. Should the else be inside the loop or handled at the end once you have searched the whole array? Is there any reason to keep going once you've found the item? A binary search isn't appropriate for this task unless the array is sorted or is large enough that the cost of sorting it and binary searching is less than a linear search would normally be. – Retired Ninja Nov 18 '18 at 03:51
  • 1
    Why do you calculate the size of the array when they give it to you as the first parameter? – Galik Nov 18 '18 at 04:00
  • 2
    Also `char*` is the wrong return type for `return "YES";`, it should be `const char*`. – Galik Nov 18 '18 at 04:05
  • 1
    Oh and if they gave you this broken function signature, you probably want to find some other coding proficiency test. – n. m. could be an AI Nov 18 '18 at 04:14
  • This is a quick test. The system automatically counts down within 90 seconds to finish it. Due to that haste, I was getting silly on arr_count part. – Hector Ta Nov 18 '18 at 05:57
  • `cout << "NO"` should be outside the loop – Damien Nov 18 '18 at 06:54
  • There's pretty much no need for loops in C++. Use [std::find](https://en.cppreference.com/w/cpp/algorithm/find) instead, passing [std::begin](https://en.cppreference.com/w/cpp/iterator/begin) and [std::end](https://en.cppreference.com/w/cpp/iterator/end) along with the value you are looking for: `auto const it{ find(begin(arr), end(arr), k) }; if (it != end(arr)) cout << "YES";`. And that's all there is to it. – IInspectable Nov 19 '18 at 09:52
  • @IInspectable : I tried to use std::find in another test, but that function only works in new version (maybe C++17, not sure if C++14 can use it). So I couldn't use it. – Hector Ta Nov 20 '18 at 00:27
  • `std::find` has been around since even before C++98. `std::begin` and `std::end` require C++14 when applied to array arguments. The latter are not required; you can pass pointers to the beginning and one element past the end of the array to `std::find` just as well. – IInspectable Nov 20 '18 at 09:23

3 Answers3

3

Here

char* (int arr_count, int arr[], int k) { }

Compiler changes int arr[] into int *arr that's because of array decaying. So when you do

 int n = sizeof(arr)/sizeof(arr[0]);

sizeof(arr) will be size of int* and n is always 1.

Hence this

for(arr_count = 0; arr_count < n; arr_count++) {
   /*  some stuff */
}

iterates only once.

Achal
  • 11,821
  • 2
  • 15
  • 37
  • Can you tell me how to avoid array decaying? In my case, do I just need to modify to n = sizeof(arr) ? – Hector Ta Nov 18 '18 at 04:01
  • 1
    @HectorTa Isn't that what `arr_count` is for? – Galik Nov 18 '18 at 04:02
  • @HectorTa If `arr_count` is the no of elements in the array, then use like `for(int itr = 0; itr < arr_count ; itr++) { }` and remove the `int n = sizeof(arr)/sizeof(arr[0]);` statement as its not needed in that case. And use `arr[itr]==k` in `if` condition. – Achal Nov 18 '18 at 04:11
  • 1
    @HectorTa - there is no way to prevent "array decaying". It is a core feature of the language. There are alternatives, such as using a standard container (e.g. `std::vector`, which can provide information about how many elements it has) instead of a raw array. – Peter Nov 18 '18 at 05:12
  • @pet: You *can* prevent array-to-pointer decay by avoiding pointer types in the function signature. You can pass arrays by value or (const) reference. This requires that the array size is known at compile time. – IInspectable Nov 19 '18 at 20:20
  • @IInspectable - an array (in the sense of something created using `SomeType array[some_size]`) cannot be passed by value. It is also not possible to have a single function that can accept an array of arbitrary size by reference (A templated function is possible, but that creates one instance of the function for every array size, and still requires the size to be known at compile time in order to use that template). I'm not about to start encouraging an obvious newbie to use such things - too many pitfalls, and a standard container is a better alternative. – Peter Nov 20 '18 at 10:11
  • @pet: Stack Overflow isn't about the OP or their ability to digest an answer. It is about the question only. While true, that you cannot pass a language-level array by value, there is `std::array` to side-step the array-to-pointer decay (which, btw., is actively being discussed to be removed from the language). All of those options require that the array size be known at compile time, and an appropriate overload set exists that can take arbitrary array sizes. Function templates with non-type template arguments are the idiomatic solution here. – IInspectable Nov 20 '18 at 10:49
2

int n = sizeof(arr)/sizeof(arr[0]);

At least this is incorrect, as your array arr decays to a pointer when passing it to function.

So sizeof(arr)/sizeof(arr[0]) is actually sizeof(pointer)/sizeof(int). And so n is always 1. And your for loop always runs for one iteration only (when arr_count == 0).

for(arr_count = 0; arr_count < n; arr_count++)

This is also incorrect - as you are not supposed to modify arr_count which is the input array size. You should use a separate variable for the loop.

for( int i = 0; i < arr_count; ++i )
artm
  • 17,291
  • 6
  • 38
  • 54
  • So I should edit n = sizeof(arr) ? I checked on geeksforgeeks website, they always do the same way. When can we use my declaration? – Hector Ta Nov 18 '18 at 04:00
  • @HectorTa I think the size of the array is in the first parameter `arr_count`. – Galik Nov 18 '18 at 04:01
  • Usually when you pass an array, you pass it a pair of parameters: (array_itself, array_size). So yes as @Galik pointed out, arr_count is the array size in this case. The order of params seems to be reverse though. – artm Nov 18 '18 at 04:04
1
 #include<iostream>

 const char* findNumber(int arr_count, int arr[], int k)
 {

   for(int i = 0; i < arr_count ; i++)
   {
      if(arr[i]==k)
        return "YES";
   }
   return "NO";
 }

 int main()
 {
    int array[] = { 2,36,42,8,85,35,225,100};
    std::cout << findNumber(sizeof(array)/sizeof(array[0]),array,43) << std::endl;
    std::cout << findNumber(sizeof(array)/sizeof(array[0]), array, 85) << std::endl;
    return 0;
 }

there you go. fixed and working fine. outputs NO and then YES.

johnathan
  • 2,315
  • 13
  • 20