The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.
The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:
If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
Otherwise, they will leave it and go to the queue’s end.
This continues until none of the queue students want to take the top sandwich and are thus unable to eat.
You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the ith sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the jth student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.
Example 1:
Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0
Explanation:
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.
Example 2:
Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3
Constraints:
1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i] is 0 or 1.
students[i] is 0 or 1.
Solution
In our initial solution, we leveraged the FIFO (First In, First Out) property of the Queue data structure to simulate the scenario where students, unable to eat their preferred sandwich, move to the end of the queue.
The outer loop of our solution was implemented using a foreach loop to iterate through the current state of the sandwiches.
C# Solution
Solution1 – Queue
public class Solution {
public int CountStudents(int[] students, int[] sandwiches) {
Queue<int> queue = new Queue<int>(students);
int tmp = 0;
foreach(var sandwich in sandwiches){
while (queue.Count>0){
var student = queue.Dequeue();
if(sandwich==student){
tmp=0;
break;
}
else{
if(tmp==queue.Count){
return queue.Count+1;
}
tmp+=1;
queue.Enqueue(student);
}
}
}
return 0;
}
}
The variable tmp serves as a counter to track the number of students checked during one iteration of the loop.
queue.Count represents the current number of students in the queue who have not yet been checked. When tmp equals queue.Count, it means all queued students have inspected the current top sandwich, and none of them prefer this type of sandwich.
Therefore, we need to return queue.Count + 1. This is because we already used queue.Dequeue() earlier to remove the first student from the queue, indicating that this student cannot eat the sandwich, so we need to include this student in the count.
var uagb_data = {"ajax_url":"https:\/\/zyrastory.com\/wp-admin\/admin-ajax.php","uagb_masonry_ajax_nonce":"3f44609536"};
var uagb_data = {"ajax_url":"https:\/\/zyrastory.com\/wp-admin\/admin-ajax.php","uagb_masonry_ajax_nonce":"3f44609536","uagb_grid_ajax_nonce":"8f1156b9e8"};
( function() {
let elements = document.querySelectorAll( '.uagb-post-grid.uagb-block-f4bc3f3d .uagb-post-pagination-wrap a' );
elements.forEach(function(element) {
element.addEventListener("click", function(event){
event.preventDefault();
const link = event.target.getAttribute('href').match( /\/page\/\d+\// )?.[0] || '';
const regex = /\d+/; // regular expression to match a number at the end of the string
const match = link.match( regex ) ? link.match( regex )[0] : 1; // match the regular expression with the link
const pageNumber = parseInt( match ); // extract the number and parse it to an integer
window.UAGBPostGrid._callAjax({"btnBorderStyle":"none","overallBorderColor":"","block_id":"f4bc3f3d","categories":"62","displayPostExcerpt":false,"displayPostComment":false,"displayPostImage":false,"imgSize":"medium","linkBox":false,"orderBy":"rand","excludeCurrentPost":true,"postPagination":true,"pageLimit":0,"imageRatio":"2-3","imgEqualHeight":true,"extended_widget_opts":{"id_base":-1,"column":{"desktop":"12","tablet":"12","mobile":"12"},"alignment":{"desktop":"default","tablet":"default","mobile":"default"},"roles":{"state":"","options":"hide"},"visibility":{"selected":"0","options":"hide","acf":{"visibility":"hide","field":"","condition":"","value":""}},"author_page":{"author_pages":{"selections":"1"}},"devices":{"options":"hide"},"days":{"options":"hide"},"dates":{"options":"hide","from":"","to":""},"styling":{"selected":"0","bg_image":"","background":"","background_hover":"","heading":"","text":"","links":"","links_hover":"","border_color":"","border_type":"","border_width":"","background_input":"","text_input":"","border_color_input":"","border_type_input":"","border_width_input":"","background_submit":"","background_submit_hover":"","text_submit":"","border_color_submit":"","border_type_submit":"","border_width_submit":"","list_border_color":"","table_border_color":""},"class":{"selected":"0","link":"","id":"","classes":"","animation":"","event":"enters","speed":"","offset":"","delay":"","logic":""},"tabselect":"0"},"btnBorderLink":true,"btnBorderRadiusLink":true,"overallBorderLink":true,"overallBorderRadiusLink":true,"inheritFromTheme":true,"postType":"post","postDisplaytext":"No post found!","taxonomyType":"category","postsToShow":6,"enableOffset":false,"postsOffset":0,"displayPostDate":true,"excerptLength":15,"displayPostAuthor":false,"displayPostTitle":true,"displayPostTaxonomy":false,"hideTaxonomyIcon":true,"taxStyle":"default","displayPostTaxonomyAboveTitle":"withMeta","imgPosition":"top","bgOverlayColor":"#000000","overlayOpacity":"50","displayPostLink":true,"newTab":false,"ctaText":"Read More","inheritFromThemeBtn":false,"buttonType":"primary","btnHPadding":"","btnVPadding":"","columns":3,"tcolumns":2,"mcolumns":1,"align":"left","width":"wide","order":"desc","rowGap":20,"rowGapTablet":20,"rowGapMobile":20,"columnGap":20,"bgType":"color","bgColor":"#f6f6f6","titleTag":"h4","titleFontSize":"","titleFontSizeType":"px","titleFontFamily":"","titleLineHeightType":"em","titleLoadGoogleFonts":false,"metaColor":"","highlightedTextColor":"#fff","highlightedTextBgColor":"#3182ce","metaFontSize":"","metaFontSizeType":"px","metaFontFamily":"","metaLineHeightType":"em","metaLoadGoogleFonts":false,"excerptColor":"","excerptFontSize":"","excerptFontSizeType":"px","excerptFontFamily":"","excerptLineHeightType":"em","excerptLoadGoogleFonts":false,"displayPostContentRadio":"excerpt","ctaBgType":"color","ctaBgHType":"color","ctaFontSize":"","ctaFontSizeType":"px","ctaFontFamily":"","ctaLineHeightType":"em","ctaLoadGoogleFonts":false,"paddingTop":20,"paddingBottom":20,"paddingRight":20,"paddingLeft":20,"contentPadding":20,"ctaBottomSpace":0,"ctaBottomSpaceTablet":0,"ctaBottomSpaceMobile":0,"imageBottomSpace":15,"titleBottomSpace":15,"metaBottomSpace":15,"excerptBottomSpace":25,"contentPaddingUnit":"px","rowGapUnit":"px","columnGapUnit":"px","excerptBottomSpaceUnit":"px","paginationSpacingUnit":"px","imageBottomSpaceUnit":"px","titleBottomSpaceUnit":"px","metaBottomSpaceUnit":"px","ctaBottomSpaceUnit":"px","paddingBtnUnit":"px","mobilePaddingBtnUnit":"px","tabletPaddingBtnUnit":"px","paddingUnit":"px","mobilePaddingUnit":"px","tabletPaddingUnit":"px","isPreview":false,"taxDivider":", ","titleLetterSpacing":"","titleLetterSpacingType":"px","metaLetterSpacing":"","metaLetterSpacingType":"px","ctaLetterSpacing":"","ctaLetterSpacingType":"px","excerptLetterSpacing":"","excerptLetterSpacingType":"px","useSeparateBoxShadows":true,"boxShadowColor":"#00000070","boxShadowHOffset":0,"boxShadowVOffset":0,"boxShadowBlur":"","boxShadowSpread":"","boxShadowPosition":"outset","boxShadowColorHover":"","boxShadowHOffsetHover":0,"boxShadowVOffsetHover":0,"boxShadowBlurHover":"","boxShadowSpreadHover":"","boxShadowPositionHover":"outset","borderWidth":"","borderStyle":"none","borderColor":"","borderRadius":"","blockName":"post-grid","equalHeight":true,"paginationBgActiveColor":"#e4e4e4","paginationActiveColor":"#333333","paginationBgColor":"#e4e4e4","paginationColor":"#777777","paginationMarkup":"","paginationLayout":"filled","paginationBorderColor":"#888686","paginationBorderSize":1,"paginationSpacing":20,"paginationAlignment":"left","paginationPrevText":"\u00ab Previous","paginationNextText":"Next \u00bb","layoutConfig":[["uagb\/post-image"],["uagb\/post-taxonomy"],["uagb\/post-title"],["uagb\/post-meta"],["uagb\/post-excerpt"],["uagb\/post-button"]],"post_type":"grid","equalHeightInlineButtons":false,"paginationType":"ajax","isLeftToRightLayout":false,"wrapperTopPadding":"","wrapperRightPadding":"","wrapperLeftPadding":"","wrapperBottomPadding":"","wrapperTopPaddingTablet":"","wrapperRightPaddingTablet":"","wrapperLeftPaddingTablet":"","wrapperBottomPaddingTablet":"","wrapperTopPaddingMobile":"","wrapperRightPaddingMobile":"","wrapperLeftPaddingMobile":"","wrapperBottomPaddingMobile":"","wrapperPaddingUnit":"px","wrapperPaddingUnitTablet":"px","wrapperPaddingUnitMobile":"px","wrapperPaddingLink":false,"wrapperAlign":"row","wrapperAlignPosition":"center","extended_widget_opts_block":{},"extended_widget_opts_state":"","extended_widget_opts_clientid":"","dateUpdated":""}, pageNumber, 'f4bc3f3d');
});
});
} )();
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};