Given a number as string, remove recurring digits from the given string. The changes must be made in-place. Expected time complexity O(n) and auxiliary space O(1).
Examples:
Input: num[] = "1299888833" Output: num[] = "12983" Input: num[] = "1299888833222" Output: num[] = "129832"
We strongly recommend you to minimize your browser and try this yourself first
This problem is similar to Run Length Encoding.
Let num[] be input number represented as character array 1) Initialize index of modified string 'j' as 0. 2) Traverse input string and do following for every digit num[i]. a) Copy current character 'num[i]' to 'num[j]' and increment i & j. b) Keep incrementing i while num[i] is same as previous digit. 3) Add string termination character at 'num[j]'
Below is the implementation of above algorithm.
C++
// C++ program to remove recurring digits from// a given number#include <bits/stdc++.h>using namespace std;/* Removes recurring digits in num[] */void removeRecurringDigits(char num[]){ int len = strlen(num); int j = 0; // Index in modified string /* Traverse digits of given number one by one */ for (int i=0; i<len; i++) { /* Copy the first occurrence of new digit */ num[j++] = num[i]; /* Remove repeating occurrences of digit */ while (i + 1 < len && num[i] == num[i+1]) i++; } /* terminate the modified string */ num[j] = '\0';}/* Driver program to test above function */int main(){ char num[] = "1299888833"; removeRecurringDigits(num); cout << "Modified number is " << num; return 0;} |
Java
// Java program to remove recurring // digits from a given numberclass GFG { /* Removes recurring digits in num[] */ static String removeRecurringDigits(char num[]) { int len = num.length; int j = 0; // Index in modified string String s = ""; /* Traverse digits of given number one by one */ for (int i = 0; i < len; i++) { /* Copy the first occurrence of new digit */ s += String.valueOf(num[i]); /* Remove repeating occurrences of digit */ while (i + 1 < len && num[i] == num[i + 1]) { i++; } } return s; } /* Driver code */ public static void main(String[] args) { char num[] = "1299888833".toCharArray(); System.out.print("Modified number is " + removeRecurringDigits(num)); }}// This code has been contributed by 29AjayKumar |
Python3
# Python3 program to remove recurring# digits from a given number# Removes recurring digits in num[]def removeRecurringDigits(num): l = len(num) # Index in modified string (i, j) = (0, 0) str = '' # Traverse digits of given # number one by one while i < l: # Copy the first occurrence # of new digit str += num[i] j += 1 # Remove repeating occurrences of digit while (i + 1 < l and num[i] == num[i + 1]): i += 1 i += 1 return str# Driver codeif __name__ == '__main__': num = '1299888833' print('Modified number is {}'.format( removeRecurringDigits(num)))# This code is contributed by rutvik_56 |
C#
// C# program to remove recurring // digits from a given numberusing System;class GFG { /* Removes recurring digits in num[] */ static String removeRecurringDigits(char []num) { int len = num.Length; int j = 0; // Index in modified string String s = ""; /* Traverse digits of given number one by one */ for (int i = 0; i < len; i++) { /* Copy the first occurrence of new digit */ s += String.Join("",num[i]); /* Remove repeating occurrences of digit */ while (i + 1 < len && num[i] == num[i + 1]) { i++; } } return s; } /* Driver code */ public static void Main() { char []num = "1299888833".ToCharArray(); Console.Write("Modified number is " + removeRecurringDigits(num)); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript program to remove recurring // digits from a given number /* Removes recurring digits in num[] */function removeRecurringDigits(num){ let len = num.length; let j = 0; // Index in modified string let s = ""; /* Traverse digits of given number one by one */ for (let i = 0; i < len; i++) { /* Copy the first occurrence of new digit */ s += (num[i]); /* Remove repeating occurrences of digit */ while (i + 1 < len && num[i] == num[i + 1]) { i++; } } return s;}/* Driver code */let num="1299888833".split("");document.write("Modified number is " + removeRecurringDigits(num));// This code is contributed by rag2127</script> |
Output
Modified number is 12983
Time complexity: O(N2) where N is the length of the string.
Auxiliary space complexity: O(1).
This article is contributed by Priyanka. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Method 2:
The main idea behind this approach is that we will traverse the string check next character of all index from 0 to n-2.
If the value at both indexes is the same then we will delete anyone of them. so, the length of the string will get reduced by 1.
Below is the implementation of the above approach.
C++
//C++ program to remove recurring //digits in a given number#include<bits/stdc++.h>using namespace std;void updatestring(string s){ int x=s.length()-2; //traversing the string for(int i=0;i<x;i++){ if(i>s.length()-2){ break; } if(s[i]==s[i+1]){ //removing character which is //occurring more than one time s.erase(s.begin()+i); i--; } } cout<<"number without recurring digits: "<<s<<endl;}//driver codeint main() {string s="1299888833222";//function callupdatestring(s);return 0;}//this code is contributed by Machhaliya Muhammad |
Java
import java.util.*;class GFG { static void updatestring(String s) { int x = s.length() - 2; // traversing the string for (int i = 0; i < x; i++) { if (i > s.length() - 2) { break; } if (s.charAt(i) == s.charAt(i + 1)) { // removing character which is // occurring more than one time s = s.substring(0, i) + s.substring(i + 1); i--; } } System.out.println("number without recurring digits: " + s); } public static void main(String[] args) { String s = "1299888833222"; // function call updatestring(s); }}// This code is contributed by Shivam Tiwari |
Python3
# Python3 program to remove recurring# digits from a given number# Removes recurring digits in num[]def removeRecurringDigits(s): x = len(s) - 2 # traversing the string for i in range(x): if(i > len(s) - 2): break if(s[i]==s[i+1]): # removing character which is # occurring more than one time s = s[:i] + s[i+1:] i = i - 1 return s# Driver codeif __name__ == '__main__': num = '1299888833' print('Modified number is {}'.format( removeRecurringDigits(num))) # This code is contributed by 111arpit1. |
C#
// C# program to remove recurring// digits from a given numberusing System;class GFG{ static string updatestring(string s){ int x = s.Length - 2; // traversing the string for(int i = 0; i<x; i++){ if(i > s.Length - 2){ break; } if(s[i] == s[i+1]) { // remove character which is // occurring more than one time s = s.Substring(0, i) + s.Substring(i+1); i -= 1; } } return s; } /* Driver code */ public static void Main() { string num = "1299888833222"; Console.Write("number without recurring degits: " +updatestring(num)); }}// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Javascript
// JavaScript Program to remove recurring// digits from a given number// Removes recurring digits in num[]function removeRecurringDigits(s){ let x = s.length - 2; // traversing the string for(let i = 0; i<x; i++){ if(i > s.length - 2) break; if(s[i] == s[i+1]){ // removing character which is // occurring more than one time s = s.substr(0, i+1) + s.substr(i+2, s.length); i = i-1; } } return s;}// Driver Codelet num = "1299888833222";document.write("Modified number is : " + removeRecurringDigits(num));// This code is contributed by Yash Agarwal |
Output
number without recurring digits: 129832
Time complexity: O(N) where N is the length of the string.
Auxiliary space complexity: O(1).
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!
