Bit Set

Easy
0/40
Average time to solve is 15m
31 upvotes
Asked in companies
LenskartGreyOrangeBusibud solutions pvt ltd

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1234
12342
Sample Output 1:
-1
 2
Explanation For Sample Input 1:
In the first test case, no digit is repeating in the string.

In the second test case, digit 2 is repeating first in the string.
Sample Input 2:
2
456746725
98768742
Sample Output 2:
4
8
Explanation For Sample Input 2:
In the first test case, digit 4 is repeating first in the string. Digits 6,7,5 are also repeating but the digit 4 is repeating first among all.

In the second test case, digit 8 is repeating first in the string.
Hint

Can you think of it by iterating each digit and storing the occurrences?

Approaches (2)
Brute Force

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:

 

  1. 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.
  2. 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.
  3. Finally if no digit repeated, Return -1.
Time Complexity

O(1),

 

Because the loop will run maximum of 11 times and we will get our answer by that time. Thus 11 denotes the constant time complexity.
 

Space Complexity

O(1), 

 

Because no extra space is used.

Code Solution
(100% EXP penalty)
Bit Set
Full screen
Console