fork download
copy 
  1. /*******************************************************************
  2. Copyright(c) 2016, Harry He
  3. All rights reserved.
  4.  
  5. Distributed under the BSD license.
  6. (See accompanying file LICENSE.txt at
  7. https://g...content-available-to-author-only...b.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
  8. *******************************************************************/
  9.  
  10.  
  11. #include <iostream>
  12.  
  13. int countRange(const int* numbers, int length, int start, int end);
  14.  
  15. int getDuplication(const int* numbers, int length)
  16. {
  17.     if(numbers == nullptr || length <= 0)
  18.         return -1;
  19.  
  20.     int start = 1;
  21.     int end = length - 1;
  22.     while(end >= start)
  23.     {
  24.         int middle = ((end - start) >> 1) + start;
  25.         int count = countRange(numbers, length, start, middle);
  26.         if(end == start)
  27.         {
  28.             if(count > 1)
  29.                 return start;
  30.             else
  31.                 break;
  32.         }
  33.  
  34.         if(count > (middle - start + 1))
  35.             end = middle;
  36.         else
  37.             start = middle + 1;
  38.     }
  39.     return -1;
  40. }
  41.  
  42. int countRange(const int* numbers, int length, int start, int end)
  43. {
  44.     if(numbers == nullptr)
  45.         return 0;
  46.  
  47.     int count = 0;
  48.     for(int i = 0; i < length; i++)
  49.         if(numbers[i] >= start && numbers[i] <= end)
  50.             ++count;
  51.     return count;
  52. }
  53.  
  54. void test(const char* testName, int* numbers, int length, int* duplications, int dupLength)
  55. {
  56.     int result = getDuplication(numbers, length);
  57.     for(int i = 0; i < dupLength; ++i)
  58.     {
  59.         if(result == duplications[i])
  60.         {
  61.             std::cout << testName << "result is: " << result << ", passed." << std::endl;
  62.             return;
  63.         }
  64.     }
  65.     std::cout << testName << " FAILED." << std::endl;
  66. }
  67.  
  68. void test1()
  69. {
  70.     int numbers[] = { 2, 2, 3, 3, 5, 5, 6, 6 };
  71.     int duplications[] = { 2, 3, 5, 6 };
  72.     test("test1", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int));
  73. }
  74.  
  75. int main()
  76. {
  77.     test1();
  78.  
  79.     return 0;
  80. }
Success #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
test1result is: 5, passed.
https://ideone.com/u9d1J2
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!