Last Updated: 8 Dec, 2020

Bit Set

Easy

Asked in companies

Solve now

Problem statement

You are given a sequence of only digits in the form of a string 'DIGIT_PATTERN', your task is to find the first repeating digit. If no digit is repeating you should return -1.

Example:

Given string of digits is 123456325. Now starting from the left, the first digit which is repeating is 3 as till 2nd 3 every digit is encountered 1st time and thus our answer for this input will be 3.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will be the string ‘DIGIT_PATTERN’, where ‘DIGIT_PATTERN’ is the input string.

Output Format:

For each test case, return the first repeating digit. Return -1 if no digit is repeated.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of.

Constraints:

1 <= T <= 10
1 <= |DIGIT_PATTERN| <= 10^5
0 <= DIGIT_PATTERN[ i ] <= 9


Where ‘DIGIT_PATTERN[i]' denotes the digit at ‘i’th index in the string ‘DIGIT_PATTERN’.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea of the approach is that we iterate for each index ‘i’ digit in the string ‘DIGIT_PATTERN’, and store the occurrence of that digit in the array/list ‘store’. At any index ‘i’, if the occurrence of the digit is already 1 in the array/list ‘store’, then we would return that digit Or else if the digit has occurred for the first time in the iteration then make the value 1 at index ‘digit’ in the array/list ‘store’, where ‘digit’ will be the digit at the ‘i’th index in the string iteration. At last, if no digit is repeated after iterating the string ‘DIGIT_PATTERN’ then return -1.

Here is the algorithm:

Declare an array/list ‘store’ of size 10 and initialize every value of ‘store’ with 0. Here, ‘store’ will maintain the occurrence of each of the 10 digits.
Run a loop for ‘i’ = 0 to the length of the ‘DIGIT_PATTERN’:
- Declare a variable ‘digit’ and assign the current digit at index ‘i’ to it, where ‘digit’ will store the current digit at ‘i’th index in the string.
- If ‘store[ digit ]’ is equal to 1:
  - Return ‘digit’.
- Else :
  - ‘Store [ digit ]’ = 1.
Finally if no digit repeated, Return -1.

Solve now

02 Approach

The basic idea of the approach is that take an integer ‘bitset’ and initialize it with 0. Now start iterating the string ‘DIGIT_PATTERN’ from the 0th index. While iterating the string, check for each digit if it's Bitwise AND with the current integer ‘bitset’ is greater than 1 then it means that the digit also appeared previously, and hence we would return that digit. Else if Bitwise AND will be zero(0) and thus the digit appeared for the first time in the iteration and hence we would set the bit corresponding to the digit as 1 and update the integer ‘bitset’ with an updated set bit corresponding to the digit. At last if no digit is repeated after iterating the string ‘digitPattern’ then return -1.

Here is the algorithm:

Declare a variable ‘bitset’ and initialize it with 0, where ‘bitset’ will store the information about which digit bit is set.
Run a loop for ‘i’ = 0 to the length of ‘DIGIT_PATTERN’:
- Declare a variable ‘digit’ and assign the current digit at index ‘i’ to it, where ‘digit’ will store the current digit at ‘i’th index in the string.
- if ‘bitset’ & ( 1<<digit) is greater than or equal to 1:
  - Return ‘digit’.
- Else :
  - Update the ‘bitset’ by making the ‘digit’ bit set in it.
Finally, if no digit repeated, Return -1.

Solve now