fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Find index of 0 to replaced with 1 to get maximum sequence
  5. // of continuous 1's using sliding window technique
  6. int findIndexofZero(int arr[], int n)
  7. {
  8.     int left = 0;            // left represents window's starting index
  9.     int count = 0;            // stores number of zeros in current window
  10.  
  11.     int max_count = 0;        // stores maximum number of 1's (including 0)
  12.     int max_index = -1;        // stores index of 0 to be replaced
  13.     int prev_zero_index=-1;    // stores index of previous zero
  14.  
  15.     // maintain a window [left..i] containing at-most one zero
  16.     for (int i = 0; i < n; i++)
  17.     {
  18.         // if current element is 0, update prev_zero_index and
  19.         // increase count of zeros in current window by 1
  20.         if (arr[i] == 0)  count++;
  21.  
  22.         // window becomes unstable if number of zeros in it becomes 2
  23.         if (count == 2)
  24.         {
  25. 			// reset leftmost 0 so that window becomes stable again
  26. 			left = prev_zero_index+1;
  27.             // decrement count as 0 is removed
  28.             count = 1;
  29.         }
  30.        //reset prev_zero_index
  31. 		if (arr[i] == 0)  prev_zero_index=i;  
  32.  
  33.         // when we reach here, the window [left..i] contains only at-most
  34.         // one zero we update maximum count and index of 0 to be replaced
  35.         // if required
  36.         if (i - left + 1 > max_count)
  37.         {
  38.             max_count = i - left + 1;
  39.             max_index = prev_zero_index;
  40.         }
  41.     }
  42.  
  43.     // return index of 0 to be replaced or -1 if array contains all 1's
  44.     return max_index;
  45. }
  46.  
  47. // main function
  48. int main()
  49. {
  50.     int arr[] = { 0, 0, 1, 0, 1, 1, 1, 0, 1, 1 };
  51.     int n = sizeof(arr) / sizeof(arr[0]);
  52.  
  53.     int index = findIndexofZero(arr, n);
  54.  
  55.     if (index != -1)
  56.         cout << "Index to be replaced is " << index;
  57.     else
  58.         cout << "Invalid input";
  59.  
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Index to be replaced is 7
https://ideone.com/z5fsd1
language:
C++14 (clang 8.0)
created:
7 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!