Remove recurring digits in a given number

Given a numer which is represented in string, write a function that will remove recurring digits in that string. If a digit is repeated consicutively, it is a recurring digit

Example

INPUT
s  = “1223334225”

OUTPUT
“123425”

Time Complexity : O(n)
Space Complexity : O(1)

Algorithm

1. Traverse the input string from second character with variable ‘i'(ie, i = 1) and build output with variable ‘j'(ie, j = 1)
a. If the current character is not equal to previous character, then make
s[j] = s[i] and increament i,j
b. Else, increament ‘i’ till the current charcter is not same as previous character

C++ Program

#include <bits/stdc++.h>
using namespace std;


void removeRecuringDigits(string s)
{
	int n = s.length();
	int j = 1;
	int i = 1;
	//Till less than length
	while(i < n)
	{
		//if curent character is not equal to previous character
		if (s[i] != s[i-1])
		{
			s[j] = s[i];
			j++;
			i++;	
		}
		//Till current character is not equal to previous character
		
		while(s[i] == s[i-1]) 
		{
		    i++;
		}
	}
	s.resize(j);
	cout<<s;
}


int main()
{
	string s = "12233321";
	removeRecuringDigits(s);
}

Try It

 

Translate »