Given a binary string S, the task is to count the minimum number of jumps required to group all 1’s together.
Examples:
Input: S = “000010011000100”
Output: 5
Explanation:
000010011000100 -> 000000111000100 requires 2 jumps.
000000111000100 -> 000000111100000 requires 3 jumps.
Hence, at least 5 jumps are required to group all 1’s together.Input: S = “100010001”
Output: 6
Explanation:
100010001 -> 000110001 requires 3 jumps.
000110001 -> 000111000 requires 3 jumps.
Approach:
We can observe that in order to minimize the number of jumps required for grouping all 1’s together, they need to be grouped near the median of their current positions. Calculate the median and the number of moves required to shift the 1’s to the nearest position of 0 in the left of the median. Perform the same operation for the right of the median.
Below is the implementation of the above approach:
C++
// C++ Program to find the minimum// number of jumps required to// group all ones together in// the binary string#include <bits/stdc++.h>using namespace std;// Function to get the// minimum jump valueint getMinJumps(string s){ // Store all indices // of ones vector<int> ones; int jumps = 0, median = 0, ind = 0; // Populating one's indices for (int i = 0; i < s.length(); i++) { if (s[i] == '1') ones.push_back(i); } if (ones.size() == 0) return jumps; // Calculate median median = ones[ones.size() / 2]; ind = median; // Jumps required for 1's // to the left of median for (int i = ind; i >= 0; i--) { if (s[i] == '1') { jumps += ind - i; ind--; } } ind = median; // Jumps required for 1's // to the right of median for (int i = ind; i < s.length(); i++) { if (s[i] == '1') { jumps += i - ind; ind++; } } // Return the final answer return jumps;}// Driver Codeint main(){ string S = "00100000010011"; cout << getMinJumps(S) << '\n'; return 0;} |
Java
// Java Program to find the minimum // number of jumps required to // group all ones together in // the binary string import java.io.*; import java.util.*; class GFG{ // Function to get the // minimum jump value public static int getMinJumps(String s) { // Store all indices // of ones Vector<Integer> ones = new Vector<Integer>(); int jumps = 0, median = 0, ind = 0; // Populating one's indices for(int i = 0; i < s.length(); i++) { if (s.charAt(i) == '1') ones.add(i); } if (ones.size() == 0) return jumps; // Calculate median median = (int)ones.get(ones.size() / 2); ind = median; // Jumps required for 1's // to the left of median for(int i = ind; i >= 0; i--) { if (s.charAt(i) == '1') { jumps += ind - i; ind--; } } ind = median; // Jumps required for 1's // to the right of median for(int i = ind; i < s.length(); i++) { if (s.charAt(i) == '1') { jumps += i - ind; ind++; } } // Return the final answer return jumps; } // Driver codepublic static void main(String[] args){ String S = "00100000010011"; System.out.println(getMinJumps(S));}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to find the minimum# number of jumps required to group # all ones together in the binary string # Function to get the# minimum jump valuedef getMinJumps(s): # Store all indices # of ones ones = [] jumps, median, ind = 0, 0, 0 # Populating one's indices for i in range(len(s)): if(s[i] == '1'): ones.append(i) if(len(ones) == 0): return jumps # Calculate median median = ones[len(ones) // 2] ind = median # Jumps required for 1's # to the left of median for i in range(ind, -1, -1): if(s[i] == '1'): jumps += ind - i ind -= 1 ind = median # Jumps required for 1's # to the right of median for i in range(ind, len(s)): if(s[i] == '1'): jumps += i - ind ind += 1 # Return the final answer return jumps# Driver Codeif __name__ == '__main__': s = "00100000010011" print(getMinJumps(s))# This code is contributed by Shivam Singh |
C#
// C# program to find the minimum // number of jumps required to // group all ones together in // the binary string using System; using System.Collections; using System.Collections.Generic;class GFG{ // Function to get the // minimum jump value public static int getMinJumps(string s) { // Store all indices // of ones ArrayList ones = new ArrayList(); int jumps = 0, median = 0, ind = 0; // Populating one's indices for(int i = 0; i < s.Length; i++) { if (s[i] == '1') ones.Add(i); } if (ones.Count== 0) return jumps; // Calculate median median = (int)ones[ones.Count / 2]; ind = median; // Jumps required for 1's // to the left of median for(int i = ind; i >= 0; i--) { if (s[i] == '1') { jumps += ind - i; ind--; } } ind = median; // Jumps required for 1's // to the right of median for(int i = ind; i < s.Length; i++) { if (s[i] == '1') { jumps += i - ind; ind++; } } // Return the final answer return jumps; } // Driver code public static void Main(string[] args) { string S = "00100000010011"; Console.Write(getMinJumps(S)); } } // This code is contributed by rutvik_56 |
Javascript
<script> // Javascript Program to find the minimum // number of jumps required to // group all ones together in // the binary string // Function to get the // minimum jump value function getMinJumps(s) { // Store all indices // of ones let ones = []; let jumps = 0, median = 0, ind = 0; // Populating one's indices for(let i = 0; i < s.length; i++) { if (s[i] == '1') ones.push(i); } if (ones.length == 0) return jumps; // Calculate median median = ones[parseInt(ones.length / 2, 10)]; ind = median; // Jumps required for 1's // to the left of median for(let i = ind; i >= 0; i--) { if (s[i] == '1') { jumps += ind - i; ind--; } } ind = median; // Jumps required for 1's // to the right of median for(let i = ind; i < s.length; i++) { if (s[i] == '1') { jumps += i - ind; ind++; } } // Return the final answer return jumps; } let S = "00100000010011"; document.write(getMinJumps(S));</script> |
Output:
10
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
