Minimum number of steps required to place all 1 s at a single index | C ++ implementation of the above approach ; Function to print minimum steps required to shift all 1 s to a single index in a binary array ; Size of array ; Used to store cumulative sum ; Initialize count ; Traverse the array in forward direction ; Steps needed to store all previous ones to ith index ; Count number of 1 s present till i - th index ; Initialize count ; Traverse the array in backward direction ; Steps needed to store all 1 s to the right of i at current index ; Count number of 1 s present after i - th index ; Print the number of steps required ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minsteps ( vector < int > & A ) { int n = A . size ( ) ; vector < int > left ( n , 0 ) , right ( n , 0 ) , res ( n , 0 ) ; int count = A [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { left [ i ] = left [ i - 1 ] + count ; count += A [ i ] ; } count = A [ n - 1 ] ; for ( int i = n - 2 ; i >= 0 ; i -- ) { right [ i ] = right [ i + 1 ] + count ; count += A [ i ] ; } for ( int i = 0 ; i < n ; i ++ ) { res [ i ] = left [ i ] + right [ i ] ; cout << res [ i ] << " ▁ " ; } cout << " STRNEWLINE " ; } int main ( ) { vector < int > A = { 1 , 0 , 1 , 0 } ; minsteps ( A ) ; }