Find which number is repeated

Question

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

This is not homework, it was asked in an interview

Answer 1

The shortest answer should be based on the answer of Vladimir. For a loop, no, but it also does not expand for variable-sized arrays. It:

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 should use good, robust code that can handle situation variables, but this is a short simple question, so it deserves a short simple answer.

Answer 2

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

This solution uses a loop, but your condition is inconsistent. Trace array means using a loop

Answer 3

Make an array of 10 bools. Each bool represents what has already happened. If you find a bool while writing the truth, the number repeats.

Answer 4

The solution I give is CommanderZ, but the only difference is that I was bored and I do not want to study, so instead I made 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 } 

See also this topic, which may be a bit similar: Given an array with multiple duplicate entries, fnd one repeat write time O (N) and constant space

And this one too: Array homework question

Answer 5

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

 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; } 

Answer 6

Try using a boolean array to indicate whether a value exists or not. Use true to indicate that a 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 does not specialize in this issue. This code has no other purpose in life, is not generalized.

Note. In this example, the cycles were not used or were not affected.
"There is always a third alternative." - Thomas Matthews