Checking numbers in an array

Question

I want to write a function that returns true if and only if in an array t of size n i have every single number from 1,2, ... n

My idea was to:

bool g(int* t, int n){
    for(int i = 0; i < n; i++){
        for(int j = n; j > 0; j--){
           if(t[i] == n)
              break;
           else
              return false;
        }
    }
    return true;
}

However this for int t[6] = {6, 2, 3, 4, 5, 1}; returns zero which is wrong as all number from 1 to 6 are in an array.

How this could be improved? Furthermore how this question could be improved?

Answer 1

My solution is giving weigths to the values, like binary digits weigths. For example:

value 1 => weight 1
value 2 => weight 2
value 3 => weight 4
value 4 => weight 8
value x => weight 1 << x-1

Then sum all of the weights, and check if satisfy sum = 2^n-1

#include <iostream>
#include <iomanip>
#include <cmath>

bool g( const int a[], int n )
{
    int long long sum = 0;
    int i = 0;
    long long int target = (1<<n)-1;

    for ( ; i < n && a[i] > 0 ; i++ ) sum += 1<<a[i]-1;

    return i == n && sum == target;
}   

int main() 
{
    const int N = 6;        
    int t[N] = { 6, 2, 3, 4, 5, 1 }; 

    std::cout << std::boolalpha << g( t, N ) << std::endl;
}

Working code here: http://ideone.com/DscXJH

This possible solution was inspired by @lcs comment in the OP.

Answer 2

Here you are

#include <iostream>
#include <iomanip>

bool g( const int a[], int n )
{
    int long long sum = 0;
    int i = 0;

    for ( ; i < n && a[i] > 0 ; i++ ) sum += a[i];

    return i == n && sum == ( long long int )n * ( n + 1 ) / 2;
}   

int main() 
{
    const int N = 6;        
    int t[N] = { 6, 2, 3, 4, 5, 1 }; 

    std::cout << std::boolalpha << g( t, N ) << std::endl;
}

The program output is

true

This function will work provided that all elements of the array are different.

As for your code then this loop

    for(int j=n;j>0;j--){
    if(t[i]==n)
      break;
    else
      return false;
    }

does not make sense.

Answer 3

Here is another solution, using STL algorithm functions:

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

bool g(int *t, int n)
{
    if ( n == 0 ) 
       return false;
    std::sort(t, t + n);
    return (t[0] == 1) &&  // first number must be 1
            (std::distance(t, std::unique(t, t + n)) == n) &&  // all must be unique
            (std::accumulate(t, t + n, 0) == (n * (n + 1)) / 2); // has to add up correctly
}

int main()
{
   int arr[] = {1,2,3,4,5,6,7};
   std::cout << g(arr, 7);
}

Live Example

After sorting the list of number, the std::unique algorithm function is used to move the non-unique items to the end of the array, and then give us a pointer to the start of this sequence of non-unique items. If all the values are unique, then std::unique will return one position past the end of the array.

That is the reason for std::distance -- it tells us if the number of numbers between the beginning and the start of the non-unique sequence is equal to the number of numbers in the entire list.

The std::accumulate simply adds up all the numbers in the sequence, and sees if the result is (n * (n+1)) / 2, which is the classic formula to find the sum of the first n consecutive integers (starting from 1).

---

Here is an even shorter solution:

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

bool g(int *t, int n)
{
    if ( n == 0 ) 
       return false;
    std::sort(t, t + n);
    return (t[0] == 1) &&  // first number must be 1
            (t[n-1] == n) && // last must be n
            (std::distance(t, std::unique(t, t + n)) == n); // all must be unique
}

---

Yet another approach:

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

bool g(int *t, int n)
{
    if ( n == 0 ) 
       return false;
    std::sort(t, t + n);
    return (t[0] == 1) &&  // first number must be 1
            (t[n-1] == n) && // last must be n
            (std::set<int>(t, t+n).size() == n); // all must be unique
}

int main()
{
   int arr[] = {1,2,3,4,5,6,7};
   std::cout << g(arr, 7);
}

Live Example

In this approach, a temporary std::set is created from the list of numbers. Since a std::set only stores unique numbers, the size() of the set after inserting all the items must be equal to n to determine if all the numbers are unique.

Answer 4

Let STL do the work.. n is non-negative

#include <set>

bool g(int *t, int n)
{
    std::set<int> s {t, t+n};
    return n > 0 && s.size() == n && *s.begin() == 1 && *s.rbegin() == n;
}

Answer 5

Try this.

#include <set>

typedef int data;
typedef std::set<data> set;

template<typename Iterator>
bool g(Iterator begin, const Iterator end) {

    set elements, expected;
    data i = 1;
    for (; begin != end; ++begin, ++i) {
        elements.insert(*begin);
        expected.insert(i);
    }

    return elements == expected;

}

Answer 6

I think, the easiest way is to count occurences. Initialize n+1 sized array "a" with zeros and increment a[ t[i] ]. It will exit on duplicates. Also make sure that t[i] is in valid range.

bool g(int* t, int n)
    {
          int* a = (int*) calloc(n+1, sizeof(int));
          for(int i=0; i<n; i++)
          {
                a[ t[i] ]++;
                if(t[i]>n || t[i]<=0 || a[ t[i] ]>1)
                      return false;
          }
          return true;
    }