CODEWITHSUNDEEP
c
Manu
Manu

Reputation: 5784

to find which number is repeated

in a array[10],there are numbers from 1 to 9 in the array and one of the number is repeated (repeated number is also between 1 and 9) how to find the repeated number without using the loop, and array can be transversed only once from top to bottom.

this is not homework, this was asked in interview

Upvotes: 4

Views: 825

Answers (6)

Thomas Matthews
Thomas Matthews

Reputation: 57698

Try using a boolean array to indicate whether a value exists or not. Use true to indicate the number exists. 

int main(void)
{
  const unsigned int array_values[10] = {1, 2, 3, 3, 4, 5, 6, 7, 8, 9};
  bool               is_resident[10] = {false};
  bool               duplicate = false;
  unsigned int       index = 0;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  duplicate = duplicate || is_resident[array[index]];
  is_resident[array[index++]] = true;
  std::cout << "Duplicate found: " << (char *)(duplicate ? "true" : "false") << std::endl;
  return 0;
}

The above code is not tested and specialized for this question. This code has no other purpose in life in is not generalized.

Note: No loops were used or harmed in this example.
"There is always a third alternative." -- Thomas Matthews

Upvotes: 0

user418748
user418748

Reputation:

The Solution I give is from CommanderZ but the only difference is that I was bored and I do not want to go study so instead I did the code.

int FindDuplicate(int index)
{
    static bool initialized = false;
    static bool Existance[10];
    if(!initialized)
    {
        for (int i = 0 ; i < 10 ; i++)
            Existance[i] = false;
        initialized = true;
    }

    if(index == -1)
        return 0;

    if(Array[index] == true)
        return index;
    else
        Array[index] = true;

    return FindDuplicate(index - 1); //edit-fix

}

Also See this thread which might be a bit similar : Given an array with multiple repeated entries, fnd one repeated entry O(N) time and constant space

And this one too : Array Homework Question

Upvotes: 0

chris
chris

Reputation: 4026

I'm bored too. Here's a solution using recursion and Vladimirs subtraction trick:

int find_dupe(int* array, int len)
{
    static int sum = 0;
    sum += array[0];

    if(len == 1)
        return sum - 45;

    return find_dupe(array+1, len-1);
}

int main()
{
    int array[10] = { 9, 2, 5, 8, 6, 7, 1, 3, 4, 2 };

    printf("dupe: %i\n", find_dupe(array, 10));

    return 0;
}

Upvotes: 0

AlastairG
AlastairG

Reputation: 4314

The shortest answer has to be based on Vladimir's answer. There is no for loop, however it is also not expandable to variable size arrays. It is:

int repeated_number = array[9]+array[8]+array[7]+array[6]+array[5]
                     +array[4]+array[3]+array[2]+array[1]+array[0]-45;

Sweet and simple, answers the question. I think, the problem is that all the people answering this question are to used to writing good sensible code that can handle variable situations, but this is a short simple question so deserves a short simple answer.

Upvotes: 8

Matěj Z&#225;bsk&#253;
Matěj Z&#225;bsk&#253;

Reputation: 17272

Make an array of 10 bools. Each bool represent whetether its respective number already occurred. If you find bool while writing a true, the number is repeated.

Upvotes: 3

Vladimir
Vladimir

Reputation: 170839

int sum = 0;
for (int i = 9; i >= 0; --i)
    sum+=array[i];
int repeatedNumber = sum - 45; // 45 = 1+...+9

This solution does use loop, but your condition is controversial - traversing array implies that the loop is used

Upvotes: 7

Related Questions