Google Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
//Written in C#
string FindMissing(int[] a)
{
if (a.Length == 0)
return "0-99";
int start = 0, end = 0;
StringBuilder result = new StringBuilder();
for (int i = 0; i < a.Length; i++)
{
if (a[i] != start)
{
end = a[i] - 1;
if (start == end)
result.Append(start.ToString() + ",");
else
result.Append(start.ToString() + "-" + end.ToString() + ",");
}
start = a[i] + 1;
}
if (start != 100)
{
end = 99;
if (start - 1 == end)
result.Append(end.ToString());
else
result.Append(start.ToString() + "-" + end.ToString());
}
return result.ToString();
}
//Written in C#
string FindMissing(int[] a)
{
if (a.Length == 0)
return "0-99";
int start = 0, end = 0;
StringBuilder result = new StringBuilder();
for (int i = 0; i < a.Length; i++)
{
if (a[i] != start)
{
end = a[i] - 1;
if (start == end)
result.Append(start.ToString() + ",");
else
result.Append(start.ToString() + "-" + end.ToString() + ",");
}
start = a[i] + 1;
}
if (start != 100)
{
end = 99;
if (start - 1 == end)
result.Append(end.ToString());
else
result.Append(start.ToString() + "-" + end.ToString());
}
return result.ToString();
}
package com.eb.corealgo;
public class MissingList {
public String getMissionList(int array[]){
String m = "";
if(array == null){
return null;
}
if(array.length == 0){
return "0-99";
}
int start = 0;
//else do the following
for(int index = 0; index < array.length ; index++){
if(array[index] != start){
m += addMissing(index,array,start) + ",";
start = array[index] + 1;
}
else {
start++;
}
}
if(array[array.length - 1] != 99){
if(array[array.length - 1] == 98){
m += " 99 ";
}
else{
m += ( array[array.length - 1] + 1) +" -"+" 99 ";
}
}
return m.substring(0,m.length()-1);
}
private String addMissing(int index,int array[],int start){
String missing = "";
missing += start;
if((start + 1) != array[index] ){
missing += " - "+(array[index] - 1);
}
return missing;
}
public static void main(String args[]){
MissingList m = new MissingList();
int a[] = {0,1,2,50,52,75,98};
System.out.println(m.getMissionList(a));
}
}
void FindSequence( vector <int> &intList )
{
int curPos = 0;
string outputString = "";
for( int n = 0; n < intList.size(); n++ )
{
if( intList[n] > curPos )
{
if( curPos == intList[n]-1)
{
outputString += to_string(curPos) + ", ";
}
else
{
outputString += to_string(curPos) + "-" + to_string(intList[n]-1)+", ";
}
curPos = intList[n] + 1;
}
}
if( intList[intList.size() - 1] != 99 )
{
outputString += to_string(curPos) + "-99";
}
else
{
outputString = outputString.substr(0, outputString.size() - 2);
}
cout << outputString << endl;
}end
private static void MissingNumberList(int a[]) {
int cnt =0;
if (a[0] != 0) {
while (cnt < a[0]) {
System.out.print(cnt + " ");
cnt++;
}
}
for (int i=0;i<a.length;i++) {
if (i+1 < a.length) {
//System.out.println(i);
int temp = a[i];
int temp1 = a[i+1];
if (temp1 - temp > 1) {
cnt = temp+1;
while(cnt < temp1) {
System.out.print(cnt + " ");
cnt++;
}
}
}
}
if (a[a.length -1] < 99) {
cnt = a[a.length -1] + 1;
while (cnt < 100) {
System.out.print(cnt + " ");
cnt++;
}
}
}
public static String getNumberRange(int[] input){
StringBuilder sb = null;
if(input.length==0){
return "0-99";
}
sb = new StringBuilder();
int index =0;
for(int i =0;i<input.length;){
if(index!= input[i]){
if(sb.length()==0){
sb.append(index + "-" + (input[i]-1));
}else{
sb.append("," + index + "-" + (input[i]-1));
}
index = input[i]+1;
i++;
continue;
}
index++;
i++;
}
if(index<99) sb.append("," + index + "-99");
if(index==99) sb.append(",99");
return sb.toString();
}
public static string ListMissing(int[] arr, int n)
{
int i, j;
StringBuilder sb = new StringBuilder();
for (i = 0, j = 0; i<n & j< 100; i++, j++)
{
if (arr[i] != j)
{
sb.Append((j).ToString());
if (arr[i]>j+1)
{
sb.Append("-" + (arr[i]-1).ToString() + ",");
j = arr[i];
}
else
sb.Append(",");
}
}
if (j != 99)
sb.Append(j.ToString()+"-99");
return sb.ToString();
}
public static string ListMissing(int[] arr, int n)
{
int i, j;
StringBuilder sb = new StringBuilder();
for (i = 0, j = 0; i<n & j< 100; i++, j++)
{
if (arr[i] != j)
{
sb.Append((j).ToString());
if (arr[i]>j+1)
{
sb.Append("-" + (arr[i]-1).ToString() + ",");
j = arr[i];
}
else
sb.Append(",");
}
}
if (j != 99)
sb.Append(j.ToString()+"-99");
return sb.ToString();
}
#include <stdio.h>
#define LAST_NUM 100
int main()
{
int i = 0;
int start = -1, end = LAST_NUM;
int input[] = {0, 1, 2,50, 52,75,90};
//int input[] = {0};
//int input[] = {3};
//int input[] = {3,5};
//int input[] = {1,3,4};
int input_size = sizeof(input) / sizeof(int);
for(i = 0; i < input_size; i++)
{
if (input[i] != start + 1)
{
end = input[i];
printf ("%d", start + 1);
if ((end - 1 ) != (start + 1))
printf(" - %d\n", end - 1);
else
printf("\n");
start = end;
}
else
start = input[i];
}
if (start != LAST_NUM - 1)
printf("%d - %d\n", start + 1, LAST_NUM - 1);
}
#include <stdio.h>
#define LAST_NUM 100
int main()
{
int i = 0;
int start = -1, end = LAST_NUM;
int input[] = {0, 1, 2,50, 52,75,90};
//int input[] = {0};
//int input[] = {3};
//int input[] = {3,5};
//int input[] = {1,3,4};
int input_size = sizeof(input) / sizeof(int);
for(i = 0; i < input_size; i++)
{
if (input[i] != start + 1)
{
end = input[i];
printf ("%d", start + 1);
if ((end - 1 ) != (start + 1))
printf(" - %d\n", end - 1);
else
printf("\n");
start = end;
}
else
start = input[i];
}
if (start != LAST_NUM - 1)
printf("%d - %d\n", start + 1, LAST_NUM - 1);
}
#include <stdio.h>
#define LAST_NUM 100
int main()
{
int i = 0;
int start = -1, end = LAST_NUM;
int input[] = {0, 1, 2,50, 52,75,90};
//int input[] = {0};
//int input[] = {3};
//int input[] = {3,5};
//int input[] = {1,3,4};
int input_size = sizeof(input) / sizeof(int);
for(i = 0; i < input_size; i++)
{
if (input[i] != start + 1)
{
end = input[i];
printf ("%d", start + 1);
if ((end - 1 ) != (start + 1))
printf(" - %d\n", end - 1);
else
printf("\n");
start = end;
}
else
start = input[i];
}
if (start != LAST_NUM - 1)
printf("%d - %d\n", start + 1, LAST_NUM - 1);
}
Public String describeMissing (int [ ] array) {
if (array.length == 0) {
return "0 - 99";
}
StringBuilder s = new StringBuilder();
if ( array[0] != 0 ){
s.append("0 - " + array[0] + ", ");
}
for (int i = 1; i < array.length; i++) {
if (array[i] - array[i - 1] != 1) {
s.append(array[i-1] + " - " + array[i] + " , ");
}
}
if (array[array.length - 1] != 99){
s.append( (array[array.length - 1] + 1) + " - 99";
}
}
// Test
//var a = new int[] { 0, 1, 2, 50, 52, 75 };
//var a = new int[] {};
//var a = new int[] { 0 };
var a = new int[] { 3, 5 };
var result = FindMissingRanges(a);
foreach (var item in result)
if (item.Item1 == item.Item2)
Console.Write(item.Item1 + ", ");
else
Console.Write(item.Item1 + "-" + item.Item2 + ", ");
Console.WriteLine();
public static IEnumerable<Tuple<int, int>> FindMissingRanges(int[] a)
{
int value = 0;
var result = new List<Tuple<int,int>>();
for (int i=0; i < a.Length; i++)
{
if (a[i] == value)
value ++;
else
{
result.Add(Tuple.Create(value, a[i] - 1));
value = a[i] + 1;
}
}
if (value < 100)
result.Add(Tuple.Create(value, 99));
return result;
}
This is so obvious that comments are really not needed.
// ZoomBA
def sanitize( range ){
#(l,r) = range.split('-')
return ( l == r ? l : range )
}
def split_range( range , n ){
#(l,r) = range.split('-')
if ( n == l ){
return sanitize( str( int(l) + 1 ) + '-' + r )
}
if ( n == r ){
return sanitize ( l + '-' + str( int(r) - 1 ) )
}
[ sanitize(l + '-' + ( n - 1) ) , sanitize( str(n+1) + '-' + r ) ]
}
def do_fancy_stuff( l ){
fold ( l , list( '0-99' ) ) ->{
res = split_range ( $.prev[-1] , $.item )
$.prev.remove( #|$.prev| - 1 )
$.prev += res // cool ?
}
}
println( do_fancy_stuff( [ 0,1,2,50,52,75 ] ) )
Since the list is sorted, we can assume that the value at n-1 will always be less then the value at n. My code compares the value at the current and previous index, and if it's greater than one, then print the range. This is not meant to be a demonstration of OO principles, but to demonstrate the algorithm. The printRanges method runs in O(n) time.
public class EmptyRangeStringPrinter {
public static void main(String args[]){
printRanges();
}
static int[] arrayOfInts = {1,2,3,4,6,8,12,45,65,94};
public static void printRanges(){
for(int i = 1; i < arrayOfInts.length; i++){
int lowerValue = arrayOfInts[i-1];
int higherValue = arrayOfInts[i];
if(higherValue - lowerValue > 1){
System.out.printf("%d - %d", lowerValue, higherValue);
System.out.println("");
}
}
}
}
/*
*Since the list is sorted, all we need to do is
*check the value at the previous index in the array.
*If the difference between a[n] and a[n-1] is greater than 1, then print the range.
*I am fully aware that this code is not object-oriented - I simply want to demonstrate the algorithm.
*
*/
public class EmptyRangeStringPrinter {
public static void main(String args[]){
printRanges();
}
static int[] arrayOfInts = {1,2,3,4,6,8,12,45,65,94};
public static void printRanges(){
for(int i = 1; i < arrayOfInts.length; i++){
int lowerValue = arrayOfInts[i-1];
int higherValue = arrayOfInts[i];
if(higherValue - lowerValue > 1){
System.out.printf("%d - %d", lowerValue, higherValue);
System.out.println("");
}
}
}
}
#Python
def finding_missing_numbers(list1):
str1 = ''
lent = len(list1)
if len(list1) == 0:
str1 = '0-99'
elif len(list1) == 1:
if list1[0] == 0:
str1 = '1-99'
elif list1[0] == 99:
str1 = '0-98'
else:
if list1[0] - 1 == 0:
str1 = '0'+ "," + str(list1[0]+1) + "-99"
elif list1[0] + 1 == 99:
str1 = '0-'+ str(list1[0]-1) +","+ '99'
else:
str1 = '0-'+ str(list1[0]-1) +","+ str(list1[0]+1) + "-99"
else:
if list1[0] != 0:
if list1[0] == 1:
str1 += '0,'
else:
str12 = '0-'+ str(list1[0]-1) +","
str1 += str12
for i in range(1,len(list1)):
temp = list1[i-1]
if list1[i] != temp + 1:
if temp + 1 == list1[i] - 1:
str12 = str(temp + 1) + ","
str1 += str12
else:
str12 = str(temp+1) + "-" + str(list1[i]-1) + ","
str1 += str12
if list1[lent - 1] != 99:
if list1[lent - 1] == 98:
str1 += '99'
else:
str12 = str(list1[lent - 1] + 1) + "-99"
str1 += str12
return str1
def main():
list1 = [0,1,2,50,52,75]
print(finding_missing_numbers(list1))
main()
def finding_missing_numbers(list1):
str1 = ''
lent = len(list1)
if len(list1) == 0:
str1 = '0-99'
elif len(list1) == 1:
if list1[0] == 0:
str1 = '1-99'
elif list1[0] == 99:
str1 = '0-98'
else:
if list1[0] - 1 == 0:
str1 = '0'+ "," + str(list1[0]+1) + "-99"
elif list1[0] + 1 == 99:
str1 = '0-'+ str(list1[0]-1) +","+ '99'
else:
str1 = '0-'+ str(list1[0]-1) +","+ str(list1[0]+1) + "-99"
else:
if list1[0] != 0:
if list1[0] == 1:
str1 += '0,'
else:
str12 = '0-'+ str(list1[0]-1) +","
str1 += str12
for i in range(1,len(list1)):
temp = list1[i-1]
if list1[i] != temp + 1:
if temp + 1 == list1[i] - 1:
str12 = str(temp + 1) + ","
str1 += str12
else:
str12 = str(temp+1) + "-" + str(list1[i]-1) + ","
str1 += str12
if list1[lent - 1] != 99:
if list1[lent - 1] == 98:
str1 += '99'
else:
str12 = str(list1[lent - 1] + 1) + "-99"
str1 += str12
return str1
def main():
list1 = [0,1,2,50,52,75]
print(finding_missing_numbers(list1))
main()
def finding_missing_numbers(list1):
str1 = ''
lent = len(list1)
if len(list1) == 0:
str1 = '0-99'
elif len(list1) == 1:
if list1[0] == 0:
str1 = '1-99'
elif list1[0] == 99:
str1 = '0-98'
else:
if list1[0] - 1 == 0:
str1 = '0'+ "," + str(list1[0]+1) + "-99"
elif list1[0] + 1 == 99:
str1 = '0-'+ str(list1[0]-1) +","+ '99'
else:
str1 = '0-'+ str(list1[0]-1) +","+ str(list1[0]+1) + "-99"
else:
if list1[0] != 0:
if list1[0] == 1:
str1 += '0,'
else:
str12 = '0-'+ str(list1[0]-1) +","
str1 += str12
for i in range(1,len(list1)):
temp = list1[i-1]
if list1[i] != temp + 1:
if temp + 1 == list1[i] - 1:
str12 = str(temp + 1) + ","
str1 += str12
else:
str12 = str(temp+1) + "-" + str(list1[i]-1) + ","
str1 += str12
if list1[lent - 1] != 99:
if list1[lent - 1] == 98:
str1 += '99'
else:
str12 = str(list1[lent - 1] + 1) + "-99"
str1 += str12
return str1
def main():
list1 = [0,1,2,50,52,75]
print(finding_missing_numbers(list1))
main()
package scratch1;
public class Main {
public static void main(String[] args) {
System.out.println(GetMissing(new int[]{0,1,2,50,52,75}, 0, 99));
}
public static String GetMissing (int[] toSkip, int start, int end)
{
if (toSkip == null) throw new IllegalArgumentException("toSkip is set to null");
if (toSkip.length == 0 ) throw new IllegalArgumentException("toSkip is an empty array");
if (toSkip[0] < start) throw new IllegalArgumentException("First element in toSkip is less than start");
if (toSkip[toSkip.length - 1] > end) throw new IllegalArgumentException("Last element in toSkip is greater than end");
StringBuilder sb = new StringBuilder();
boolean appended = false;
//Check first range
if( toSkip[0] > start )
{
//Issue here about toSkip[0] being int.minValue;
sb.append(GetInclusiveRange(start, toSkip[0] - 1));
appended = true;
}
//Check ranges in between
for(int i = 1; i < toSkip.length; i++)
{
if (toSkip[i] - toSkip[i - 1] > 1)
{
if (appended) {
sb.append(',');
}
//There's a missing range
sb.append(GetExclusiveRange(toSkip[i - 1], toSkip[i]));
appended = true;
}
}
//Check last range
if (toSkip[toSkip.length - 1] < end)
{
if (appended)
{
sb.append(',');
}
//Issue here about toSkip[0] being int.minValue;
sb.append(GetInclusiveRange(toSkip[toSkip.length - 1], end));
appended = true;
}
return sb.toString();
}
private static String GetInclusiveRange(int start, int end)
{
if (start == end) return Integer.toString(start);
if (end - start == 1) return start + "," + end;
return start + "-" + end;
}
private static String GetExclusiveRange(int start, int end)
{
if (start == end || start + 1 == end) return "";
if (start + 1 == end - 1) return Integer.toString(start + 1);
if ((end - 1) - (start + 1) == 1) return (start + 1) + "," + (end - 1);
return (start + 1) + "-" + (end - 1);
}
}
Simple look-ahead python implementation. If difference between current index and next is greater than two, append a range. Else If greater than one, append a single element. Repeat for final index and the max bound (99 in this case)
...: def missing(l):
...: out = ""
...: for i in range(len(l)):
...: if i < len(l)-1:
...: if l[i+1]-l[i] > 2:
...: out += str(l[i]+1) + "-" + str(l[i+1]-1) + ","
...: elif l[i+1]-l[i] > 1:
...: out += str(l[i]-1) + ','
...: else:
...: if l[i] < 99:
...: if 99-l[i] > 2:
...: out += str(l[i]+1) + "-99"
...: elif 99-l[i] > 1:
...: out += "99"
...: return out
public class ListRange {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(0,1,2,50,52,75);
System.out.println(listRanges(list));
}
public static String listRanges(List<Integer> list){
int i = 0;
int start = -1;
//int end = -1;
StringBuilder builder = new StringBuilder();
int max = list.get(list.size() - 1);
int lim = 100;
while (i < 100 && i <= max){
if (!list.contains(i)){
if (start == -1){
start = i;
if (list.contains(i + 1)){
builder.append(start + ",");
start = -1;
i++;
}
}
}
else if (start != -1){
builder.append(start + "-" + (i - 1) + ",");
start = -1;
}
i++;
}
builder.append((max + 1) + "-" + (lim - 1));
return builder.toString();
}
}
int main(int argc, char *argv[])
{
vector<int> input = {};
int arr[100] = {0,1,2,50,79, 52, 75};
for(int i = 0; i < input.size();i++)
{
arr[input[i]] = 1;
}
for(int j = 0; j < 100; )
{
while(arr[j] == 1)
j++;
int left = j;
int right = j+1;
while(right < 100 && arr[right] == 0)
right++;
if(left == right-1)
cout << left <<" ,";
else
cout << left<< "-" << right-1 << ", ";
j = right;
}
return 0;
}
{
int main(int argc, char *Argv[])
{
vector<int> input = {};
int arr[100] = {0};
for(int i = 0; i < input.size();i++)
{
arr[input[i]] = 1;
}
for(int j = 0; j < 100; )
{
while(arr[j] == 1)
j++;
int left = j;
int right = j+1;
while(right < 100 && arr[right] == 0)
right++;
if(left == right-1)
cout << left <<" ,";
else
cout << left<< "-" << right-1 << ", ";
j = right;
}
return 0;
}
int main(int argc, char *Argv[])
{
vector<int> input = {};
int arr[100] = {0};
for(int i = 0; i < input.size();i++)
{
arr[input[i]] = 1;
}
for(int j = 0; j < 100; )
{
while(arr[j] == 1)
j++;
int left = j;
int right = j+1;
while(right < 100 && arr[right] == 0)
right++;
if(left == right-1)
cout << left <<" ,";
else
cout << left<< "-" << right-1 << ", ";
j = right;
}
return 0;
}
public class GFG {
public static void main(String[] args) {
String ans, result = " ";
int flag = 0;
int visit = 0;
int[] number = {1, 2, 50, 52, 75};
int ub = 99;
Integer lb = 0;
int n = number.length;
System.out.println("length:" + n);
int i, count = 0;
for (i = 0; i < n - 1; i++) {
count++;
int j = i + 1;
int difference = number[j] - number[i];
ans = " ";
if (lb != number[0] && visit == 0) {
ans = ans + lb.toString();
result = result + ans + ",";
ans = " ";
visit = 1;
}
if (difference > 1) {
flag = 1;
if (difference == 2) {
ans = ans + (number[j] - 1);
} else {
Integer missing_num = number[i] + 1;
ans = ans + missing_num.toString() + "-" + (number[j] - 1);
}
}
if (flag == 1) {
result = result + ans + ",";
}
}
count++;
System.out.println(" count \t" + count);
if (count == number.length) {
ans = " ";
ans = ans + (number[i] + 1) + "-" + ub;
result = result + ans;
}
System.out.println("Output is:" + result);
}
}
public class GFG {
public static void main(String[] args) {
String ans, result = " ";
int flag = 0;
int visit = 0;
int[] number = {1, 2, 50, 52, 75};
int ub = 99;
Integer lb = 0;
int n = number.length;
System.out.println("length:" + n);
int i, count = 0;
for (i = 0; i < n - 1; i++) {
count++;
int j = i + 1;
int difference = number[j] - number[i];
ans = " ";
if (lb != number[0] && visit == 0) {
ans = ans + lb.toString();
result = result + ans + ",";
ans = " ";
visit = 1;
}
if (difference > 1) {
flag = 1;
if (difference == 2) {
ans = ans + (number[j] - 1);
} else {
Integer missing_num = number[i] + 1;
ans = ans + missing_num.toString() + "-" + (number[j] - 1);
}
}
if (flag == 1) {
result = result + ans + ",";
}
}
count++;
System.out.println(" count \t" + count);
if (count == number.length) {
ans = " ";
ans = ans + (number[i] + 1) + "-" + ub;
result = result + ans;
}
System.out.println("Output is:" + result);
}
}
public class MissingInt {
public static void main(String[] args){
int sortedList[]={8,25,27,78,89};
int sortedList2[]={3,5};
String finalResult="";
finalResult=getMissingInts(sortedList2);
System.out.println(finalResult);
}
public static String getMissingInts(int list[]){
StringBuilder sb=new StringBuilder();
int count=0;
if(list.length==1&&list[0]==0){
sb.append("1-99, ");
}else if(list.length==0){
sb.append("0-99, ");
}else if(list.length==1&&list[0]==99){
sb.append("0-98, ");
}
else if(list.length>1) {
switch (list[0]) {
case 0:
sb.append("");
break;
case 1:
sb.append("0");
break;
default:
sb.append("0-").append(list[0]-1);
break;
}
for(int i=0;i<list.length-1;i++){
if(list[i+1]-list[i] > 1&& list[i+1]-list[i]==2 ){
sb.append(",").append(list[i]+1).append("");
}else if(list[i+1]-list[i] > 1){
sb.append(",").append(list[i]+1).append("-").append(list[i+1]-1).append("");
}
count=count+1;
}
switch (list[count]) {
case 98:
sb.append(99);
break;
case 99:
sb.append("");
break;
default:
sb.append(",").append(list[count]+1).append("-99");
break;
}
}
return sb.toString();
}
}
public class MissingInt {
public static void main(String[] args){
int sortedList[]={8,25,27,78,89};
int sortedList2[]={3,5};
String finalResult="";
finalResult=getMissingInts(sortedList2);
System.out.println(finalResult);
}
public static String getMissingInts(int list[]){
StringBuilder sb=new StringBuilder();
int count=0;
if(list.length==1&&list[0]==0){
sb.append("1-99, ");
}else if(list.length==0){
sb.append("0-99, ");
}else if(list.length==1&&list[0]==99){
sb.append("0-98, ");
}
else if(list.length>1) {
switch (list[0]) {
case 0:
sb.append("");
break;
case 1:
sb.append("0");
break;
default:
sb.append("0-").append(list[0]-1);
break;
}
for(int i=0;i<list.length-1;i++){
if(list[i+1]-list[i] > 1&& list[i+1]-list[i]==2 ){
sb.append(",").append(list[i]+1).append("");
}else if(list[i+1]-list[i] > 1){
sb.append(",").append(list[i]+1).append("-").append(list[i+1]-1).append("");
}
count=count+1;
}
switch (list[count]) {
case 98:
sb.append(99);
break;
case 99:
sb.append("");
break;
default:
sb.append(",").append(list[count]+1).append("-99");
break;
}
}
return sb.toString();
}
}
public class FindRange {
public static void main(String[] args) {
Integer[] n = { 0, 1, 2, 50, 52, 75 };
boolean[] b = new boolean[100];
int m = 0;
for (int i = 0; i < n.length; i++) {
b[n[i]] = true;
}
while (m < 100) {
if (!b[m]) {
Integer k = m;
String tmp = "";
m++;
while (m < 100 && !b[m]) {
tmp = "_" + m;
m++;
}
System.out.println(k + tmp);
}
m++;
}
}
}
public class FindRange {
public static void main(String[] args) {
Integer[] n = { 0, 1, 2, 50, 52, 75 };
boolean[] b = new boolean[100];
int m = 0;
for (int i = 0; i < n.length; i++) {
b[n[i]] = true;
}
while (m < 100) {
if (!b[m]) {
Integer k = m;
String tmp = "";
m++;
while (m < 100 && !b[m]) {
tmp = "_" + m;
m++;
}
System.out.println(k + tmp);
}
m++;
}
}
}
public class Solution {
static String missingSegments(int[] ary) {
int len = ary.length;
String retVal = "";
int lastSeen = -1;
for (int i = 0; i < len; i++) {
if (lastSeen == -1 && ary[i] > 0) {
retVal = "0-" + (ary[i] - 1);
}
else {
if (lastSeen < ary[i] - 1) {
if (lastSeen == (ary[i] - 2)) {
if (retVal.length() > 0) {
retVal += ",";
}
retVal += (lastSeen + 1);
} else {
if (retVal.length() > 0) {
retVal += ",";
}
retVal += ((lastSeen + 1) + "-" + (ary[i] - 1));
}
}
}
lastSeen = ary[i];
}
if (lastSeen < 99) {
if (retVal.length() > 0) {
retVal += ",";
}
retVal += (lastSeen + 1);
if (lastSeen < 98) {
retVal += "-" + 99;
}
}
return retVal;
}
public static void main(String[] args) {
int[][] arys = {
{ 0 }, //"1-99"
{ 3, 5 },//"0-2,4,6-99"
{ 2, 7, 9, 98 },//"0-1,3-6,8,10-97,99"
{ 2, 7, 8, 9, 98 }, //"0-1,3-6,10-97,99"
{98 }, //"0-97,99"
{98, 99}, //"0-97"
{ 99 }, //"0-98"
{ 0, 1, 2, 50, 52, 75 }}; //"3-49,51,53-74,76-99"
for (int i = 0; i < arys.length; i++) {
System.out.println(missingSegments(arys[i]));
}
}
}
static void Main(string[] args)
{
int[] nums = { 0, 1, 50, 60, 61, 70, 75, 99,100 };
StringBuilder missing = new StringBuilder("");
int rangeDifference = 0;
int previous = 0;
previous = nums[0];
for (int i=0; i < nums.Length; i++)
{
if (i >= 1)
{
rangeDifference = nums[i]-previous;
if (rangeDifference != 0)
{
if (rangeDifference > 1)
{
missing.Append(String.Format("{0}-{1},",(previous+1).ToString(), (nums[i]-1).ToString()));
}
else
{
missing.Append((previous+1).ToString() + ",");
}
}
}
if (nums[i] == 99) break; //take this out for an extensibile list
previous = nums[i];
}
}
static void Main(string[] args)
{
int[] nums = { 0, 1, 50, 60, 61, 70, 75, 99,100 };
StringBuilder missing = new StringBuilder("");
int rangeDifference = 0;
int previous = 0;
previous = nums[0];
for (int i=0; i < nums.Length; i++)
{
if (i >= 1)
{
rangeDifference = nums[i]-previous;
if (rangeDifference != 0)
{
if (rangeDifference > 1)
{
missing.Append(String.Format("{0}-{1},",(previous+1).ToString(), (nums[i]-1).ToString()));
}
else
{
missing.Append((previous+1).ToString() + ",");
}
}
}
if (nums[i] == 99) break; //take this out for an extensibile list
previous = nums[i];
}
}
static void Main(string[] args)
{
int[] nums = { 0, 1, 50, 60, 61, 70, 75, 99,100 };
StringBuilder missing = new StringBuilder("");
int rangeDifference = 0;
int previous = 0;
previous = nums[0];
for (int i=0; i < nums.Length; i++)
{
if (i >= 1)
{
rangeDifference = nums[i]-previous;
if (rangeDifference != 0)
{
if (rangeDifference > 1)
{
missing.Append(String.Format("{0}-{1},",(previous+1).ToString(), (nums[i]-1).ToString()));
}
else
{
missing.Append((previous+1).ToString() + ",");
}
}
}
if (nums[i] == 99) break; //take this out for an extensibile list
previous = nums[i];
}
}
def miss_am(a):
out = '"'
ipp = 0
if len(a) == 0:
out += '0-99"'
else:
if a[0] != 0:
if a[0] > 1:
out += '0-{},'.format(a[0] - 1)
elif a[0] == 1:
out += '0,'
for p, n in zip(a[:len(a) - 1], a[1:]):
if n - p > 2:
out += '{}-{},'.format(p + 1, n - 1)
elif n - p > 1:
out += '{},'.format(p + 1)
al = a[len(a) - 1]
if al != 99:
if 99 - al > 2:
out += '{}-99'.format(al + 1)
elif 99 - al > 1:
out += '99'
else:
out = out[:-1]
out += '"'
return out
func = miss_am
b = [[0,1,3,5,9,88,99],
[0,1,3,5,9,88,99],
[0,1,3,5,9,88],
[],
[0],
[3],
[5,99]
]
for i in range(len(b)):
print(func(b[i]))
String MissingNumbers(List<int> L){
StringBuilder sb = new StringBuilder();
var nextvalue = 0;
foreach (var num in L)
{
var cur = L.IndexOf(num);
if (num == L.LastOrDefault())
{
nextvalue = 100;
}
else
{
nextvalue = L.ElementAt(cur + 1);
}
if (num != nextvalue - 1)
{
if (num + 1 == nextvalue - 1)
{
sb.Append((num + 1).ToString() + ',');
}
else if (num != nextvalue - 1)
{
if (nextvalue - 1 == 99)
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString());
}
else
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString() + ',');
}
}
}
}
return sb.ToString();
}
String MissingNumbers(List<int> L){
StringBuilder sb = new StringBuilder();
var nextvalue = 0;
foreach (var num in L)
{
var cur = L.IndexOf(num);
if (num == L.LastOrDefault())
{
nextvalue = 100;
}
else
{
nextvalue = L.ElementAt(cur + 1);
}
if (num != nextvalue - 1)
{
if (num + 1 == nextvalue - 1)
{
sb.Append((num + 1).ToString() + ',');
}
else if (num != nextvalue - 1)
{
if (nextvalue - 1 == 99)
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString());
}
else
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString() + ',');
}
}
}
}
return sb.ToString();
}
public String MissingNumbers(List<int> L) {
StringBuilder sb = new StringBuilder();
var nextvalue = 0;
foreach (var num in L)
{
var cur = L.IndexOf(num);
if (num == L.LastOrDefault())
{
nextvalue = 100;
}
else
{
nextvalue = L.ElementAt(cur + 1);
}
if (num != nextvalue - 1)
{
if (num + 1 == nextvalue - 1)
{
sb.Append((num + 1).ToString() + ',');
}
else if (num != nextvalue - 1)
{
if (nextvalue - 1 == 99)
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString());
}
else
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString() + ',');
}
}
}
}
return sb.ToString();
}
public String MissingNumbers(List<int> L)
{
StringBuilder sb = new StringBuilder();
var nextvalue = 0;
foreach (var num in L)
{
var cur = L.IndexOf(num);
if (num == L.LastOrDefault())
{
nextvalue = 100;
}
else
{
nextvalue = L.ElementAt(cur + 1);
}
if (num != nextvalue - 1)
{
if (num + 1 == nextvalue - 1)
{
sb.Append((num + 1).ToString() + ',');
}
else if (num != nextvalue - 1)
{
if (nextvalue - 1 == 99)
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString());
}
else
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString() + ',');
}
}
}
}
return sb.ToString();
}
public String MissingNumbers(List<int> L)
{
StringBuilder sb = new StringBuilder();
var nextvalue = 0;
foreach (var num in L)
{
var cur = L.IndexOf(num);
if (num == sorted.LastOrDefault() && num==100)
{
nextvalue = 100;
break;
}
if (num == sorted.LastOrDefault() && num != 100)
{
nextvalue = 100;
sb.Append((num + 1).ToString() + '-'+(nextvalue-1).ToString());
break;
}
else
{
nextvalue = L.ElementAt(cur + 1);
}
if (num != nextvalue - 1)
{
if (num + 1 == nextvalue - 1)
{
sb.Append((num + 1).ToString() + ',');
}
else if (num != nextvalue - 1)
{
if (nextvalue - 1 == 99)
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString());
}
else
{
sb.Append((num + 1).ToString() + '-' + (nextvalue - 1).ToString() + ',');
}
}
}
}
return sb.ToString();
}
//This code is in c++
#include <iostream>
#include <string>
using namespace std;
string getNumbersInclusive(int iStart, int iEnd){
int iSubst = iEnd - iStart;
if(iSubst == 2){
return to_string(iEnd - 1) + " ";
}else if(iSubst > 2){
return to_string(iStart + 1) + "-" + to_string(iEnd - 1) + " ";
}else
return "";
}
string findMissingNumbers(int iArr[], int iLength){
if(iLength == 0)
return "0-99";
else{
string sMissingNumbers = "";
int iLast = -1;
//Generate ranges of numbers and add them to the sMissingNumbers string
for(int i = 0; i < iLength; i++){
//If there are numbers between the last one and the one being checked right
//now, generate them and add them to the string being returned.
sMissingNumbers += getNumbersInclusive(iLast, iArr[i]);
iLast = iArr[i];
}
//Generate numbers from the last number to 100 inclusively
sMissingNumbers += getNumbersInclusive(iLast, 100);
return sMissingNumbers;
}
}
def find_gaps(a):
start = 0
end = 99
gaps = []
for x in a:
if x == start + 1:
gaps.append(str(start))
elif x is not start:
gaps.append(str(start) + "-" + str(x-1))
start = x + 1
if start == end:
gaps.append(str(start))
elif start < end:
gaps.append(str(start) + "-" + str(end))
return gaps
arr = [1,2, 3, 5, 10,11, 88, 98]
print find_gaps(arr)
import java.util.*;
import java.lang.*;
import java.io.*;
/*
Examples:
[] “0-99”
[0] “1-99”
[3, 5] “0-2,4,6-99”
[0, 1, 2, 50, 52, 75] "3-49,51,53-74,76-99"
*/
class FindMissingNumbers {
public static void main (String[] args) {
int[] array = {0,1,2,50,52,75,98};
StringBuilder result = new StringBuilder();
int lastValue = -1;
for (int i=0; i< array.length; i++) {
if (i == 0 && array[i] != 0) {
int value = --array[i];
value--;
if (value != 0) result.append("0-");
result.append(value+",");
lastValue = array[i];
}
if (array[i] - lastValue == 1) {
lastValue = array[i];
} else if (array[i] - lastValue == 2) {
int value = array[i];
value--;
result.append(value+",");
lastValue = array[i];
} else if (array[i] - lastValue > 2) {
lastValue++;
int value = array[i];
value--;
result.append(lastValue+"-"+value+",");
lastValue = array[i];
}
}
if (lastValue != 99) {
lastValue++;
if (lastValue != 99) result.append(lastValue+"-99");
else result.append("99");
}
System.out.println(result);
}
}
def print_missing(arr, min_el = 0, max_el = 99):
current_missing_start = min_el
missing_strings = []
for i in xrange(len(arr)+1):
el = arr[i] if i < len(arr) else max_el+1
if el > current_missing_start + 1:
missing_strings.append(str(current_missing_start)+'-'+str(el-1))
elif el == current_missing_start + 1:
missing_strings.append(str(current_missing_start))
current_missing_start = el+1
print ','.join(missing_strings)
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
std::string FindMissing(std::vector<int> arr)
{
int start = 0;
int end = 99;
std::stringstream stream;
for (unsigned i = 0; i < arr.size(); i++)
{
if (start != arr[i])
{
int last = arr[i] - 1;
if (start == last)
stream << start << ",";
else
stream << start << "-" << last << ",";
start = arr[i] + 1;
}
else
{
start = arr[i] + 1;
}
}
if (start != 100)
{
if (start == end)
stream << start;
else
stream << start << "-" << end;
}
return stream.str();
}
int main()
{
std::vector<int> a{ 3, 5 };
std::cout << FindMissing(a) << std::endl;
std::vector<int> b{};
std::cout << FindMissing(b) << std::endl;
std::vector<int> c{ 0, 1, 2, 50, 52, 75 };
std::cout << FindMissing(c) << std::endl;
return 0;
}
Here lies a working code:
#include<bits/stdc++.h>
#include<string>
using namespace std;
string ntos(int number)
{
stringstream ss;
ss<<number;
return ss.str();
}
string append(string x,int start,int end)
{
cout<<start<<" "<<end<<endl;
// stringstream convert;
if(start==end)
{
// string a=to_string(start);
x.append(ntos(start));
}
else
{
x.append(ntos(start));
x.append("-");
x.append(ntos(end));
}
return x;
}
main()
{
int n;
cin>>n;
int ar[n];
for(int i=0;i<n;i++)
{
cin>>ar[i];
}
int pos=0;
string x="";
for(int i=0;i<n;i++)
{
if(x.length()!=0)
{
x.append(",");
}
int start=-1,end=-1;
if(i!=0)
{
if(ar[i-1]+1!=ar[i])
{
start=ar[i-1]+1;
end=ar[i]-1;
}
}
else
{
if(ar[i]!=0)
{
start=0;
end=ar[i]-1;
}
}
if(start!=-1 && end!=-1)
x=append(x,start,end);
}
if(ar[n-1]!=99)
{
x.append(",");
int start=ar[n-1]+1;
int end=99;
x=append(x,start,end);
}
cout<<x<<endl;
}
def getMissingSequence(x):
ret_val = []
lower_bound = 0
upper_bound = 99
if not x:
ret_val.append((lower_bound, upper_bound))
return ret_val
prev = x[0]
if prev - lower_bound == 1:
ret_val.append((prev-1, ))
elif prev - lower_bound > 1:
ret_val.append((lower_bound, prev-1))
for each in x[1:]:
if each - (prev+1) == 1:
ret_val.append((prev+1,))
elif each - (prev+1) > 1:
ret_val.append((prev+1, each-1))
prev = each
if upper_bound-prev != 1:
if upper_bound != prev:
ret_val.append((prev+1, upper_bound))
else:
ret_val.append((prev+1,))
return ret_val
",".join("-".join(map(str, each)) for each in getMissingSequence([0, 2, 4, 96, 98]))
def getMissingSequence(x):
ret_val = []
lower_bound = 0
upper_bound = 99
if not x:
ret_val.append((lower_bound, upper_bound))
return ret_val
prev = x[0]
if prev - lower_bound == 1:
ret_val.append((prev-1, ))
elif prev - lower_bound > 1:
ret_val.append((lower_bound, prev-1))
for each in x[1:]:
if each - (prev+1) == 1:
ret_val.append((prev+1,))
elif each - (prev+1) > 1:
ret_val.append((prev+1, each-1))
prev = each
if upper_bound-prev != 1:
if upper_bound != prev:
ret_val.append((prev+1, upper_bound))
else:
ret_val.append((prev+1,))
return ret_val
",".join("-".join(map(str, each)) for each in getMissingSequence([0, 2, 4, 96, 98]))
#include <vector>
#include <string>
#include <iostream>
using namespace std;
void printRanges(std::vector<int> arr) {
if (arr[arr.size() - 1] != 100) {
arr.push_back(100);
}
for (int i = 1; i < arr.size(); i++) {
int lowerValue = arr[i - 1];
int higherValue = arr[i];
int delta = higherValue - lowerValue;
if (delta == 2) {
printf("%d; ", lowerValue + 1);
}
else if (delta > 2) {
printf("%d - %d; ", lowerValue + 1, higherValue - 1);
}
}
}
// Driver program to test above function
int main()
{
std::vector<int> arr = { 1,2,3,4,6,8,12,45,65,94 };
printRanges(arr);
return 0;
}
std::string findRanges(std::set<int> S)
{
std::string str;
int prev = 0;
S.insert(100);
for(int i : S)
{
if(prev + 1 == i)
str += std::to_string(prev) + ",";
else if(prev + 1 < i)
str += std::to_string(prev) + "-" + std::to_string(i - 1) + ",";
prev = i + 1;
}
str.pop_back();
return str;
}
void printseq(int* arr,int len)
{
int c = 0;
int i = 0;
string s = "";
for (; i < len; ++i)
{
if (arr[i] != c)
{
cout << s;
cout << c;
if (arr[i] - c > 2)
cout << "-" << arr[i] - 1;
s = ',';
}
if(i+1 < len)
c = arr[i]+1;
}
if (c < 99)
cout << s << arr[i - 1] + 1 << "-" << 99;
cout << endl;
}
void printseq(int* arr,int len)
{
int c = 0;
int i = 0;
string s = "";
for (; i < len; ++i)
{
if (arr[i] != c)
{
cout << s;
cout << c;
if (arr[i] - c > 2)
cout << "-" << arr[i] - 1;
s = ',';
}
if(i+1 < len)
c = arr[i]+1;
}
if (c < 99)
cout << s << arr[i - 1] + 1 << "-" << 99;
cout << endl;
}
def funct(inp):
if (inp == []):
return "0-99"
out = ""
for i in range(len(inp)):
if (i == 0 and inp[i] != 0):
out += "0-" + str(inp[0]-1) + ","
if (i == (len(inp)-1) and inp[i] != 99):
out += str(inp[len(inp)-1] + 1) + "-99"
elif (inp[i] + 1 != inp[i+1]):
if (inp[i] + 1 == inp[i+1] -1):
out += str(inp[i]+1) + ","
else:
out += str(inp[i]+1) + "-" + str(inp[i+1]-1) + ","
return out
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
void find_missing_range(const std::vector<int>& num_list, std::string& miss_range_str)
{
int i;
int start = 0;
int end = 99;
int arr[100];
std::ostringstream oss;
string str;
for (i = start; i <= end; i++)
arr[i]=i;
i = start;
static int j = i;
for (; j < num_list.size() && i <= end; j++, i++)
{
if ( num_list[j] > arr[i])
{
if (num_list[j] != arr[i]+1)
oss << i <<"-"<<num_list[j] - 1<<",";
else
oss <<i<<",";
i = num_list[j];
j++;
break;
}
}
if (!num_list.size())
oss<<start<<"-"<<end;
if (num_list.size() > 0 && num_list[num_list.size() - 1] < end)
oss <<num_list[num_list.size()-1] + 1<<"-"<<end;
miss_range_str = oss.str();
}
int main()
{
std::vector<int> num_list{3, 5};
std::string miss_list;
find_missing_range(num_list, miss_list);
cout <<"miss_list: "<<miss_list<<endl;
return 0;
}
let input = [0, 1, 2, 50, 52, 75, 99];
let output = [];
for (let i = 0; i < input.length; i++) {
if (input[i+ 1]) {
if ((input[i] + 1) !== input[i + 1]) {
(input[i] + 1) === (input[i+ 1] - 1)
? output.push(`${input[i] + 1}`)
: output.push(`${input[i] + 1} - ${input[i+ 1] - 1}`);
}
}
}
console.log(output);
let input = [0, 1, 2, 50, 52, 75, 99];
let output = [];
for (let i = 0; i < input.length; i++) {
if (input[i+ 1]) {
if ((input[i] + 1) !== input[i + 1]) {
(input[i] + 1) === (input[i+ 1] - 1)
? output.push(`${input[i] + 1}`)
: output.push(`${input[i] + 1} - ${input[i+ 1] - 1}`);
}
}
}
console.log(output);
public class FindMissingRange {
private int[] holder = new int[100];
private int start = -1;
private String result = "", s;
private String findRange(List<Integer> nums) {
if(nums == null || nums.size() == 0)return "0-99";
for(int n : nums){
holder[n] = 1;
}
for (int i = 0; i<100; i++) {
if(holder[i]==0) {
if(start == -1) start = i;
} else {
if(start != -1) {
if(i-start == 1) s = ""+start;
else s = start + "-" + (i-1);
result += (result.equals("")?"":",")
+ s;
start = -1;
}
}
}
if(start != -1)
result += (result.equals("")?"":",")
+ ((99-start != 0)?start + "-":"") + 99;
return result;
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
list.add(50);
list.add(52);
list.add(75);
list.add(98);
System.out.println(new FindMissingRange().findRange(list));
}
}
//Written in C#
- Trndp November 14, 2016string FindMissing(int[] a) { if (a.Length == 0) return "0-99"; int start = 0, end = 0; StringBuilder result = new StringBuilder(); for (int i = 0; i < a.Length; i++) { if (a[i] != start) { end = a[i] - 1; if (start == end) result.Append(start.ToString() + ","); else result.Append(start.ToString() + "-" + end.ToString() + ","); } start = a[i] + 1; } if (start != 100) { end = 99; if (start - 1 == end) result.Append(end.ToString()); else result.Append(start.ToString() + "-" + end.ToString()); } return result.ToString(); }