Check if Queue Elements are pairwise consecutive | Set-2
Given a Queue of integers. The task is to check if consecutive elements in the queue are pairwise consecutive.
Examples:
Input: 1 2 5 6 9 10 Output: Yes Input: 2 3 9 11 8 7 Output: No
Approach :
- Take a variable n to store size of queue.
- Push an element to the queue which acts as marker.
- Now, If size of queue is odd, start popping a pair while n > 2. Also, while popping these pairs, check for their difference and decrease n by 2, if there difference is not equal to 1, set flag to false.
- If size of queue is even, start popping a pair while n > 1. Also, while popping these pairs, check for their difference and decrease n by 2, if their difference is not equal to 1, set flag to false.
- Finally, check flag, if it is true, it means elements in the queue are pairwise sorted, else not.
Below is the implementation of above approach:
C++
// C++ program to check if successive // pair of numbers in the queue are // consecutive or not #include <bits/stdc++.h> using namespace std; // Function to check if elements are // pairwise consecutive in queue bool pairWiseConsecutive(queue< int > q) { // Fetching size of queue int n = q.size(); // Pushing extra element to the queue // which acts as marker q.push(INT_MIN); // Result flag bool result = true ; // If number of elements in the // queue is odd pop elements while // its size is greater than 2. // Else, pop elements while its // size is greater than 1 if (n % 2 != 0) { while (n > 2) { int x = q.front(); q.pop(); q.push(x); n--; int y = q.front(); q.pop(); q.push(y); n--; if ( abs (x - y) != 1) { result = false ; } } // Popping the last element of queue // and pushing it again. // Also, popping the extra element // that we have pushed as marker q.push(q.front()); q.pop(); q.pop(); } else { while (n > 1) { int x = q.front(); q.pop(); q.push(x); n--; int y = q.front(); q.pop(); q.push(y); n--; if ( abs (x - y) != 1) { result = false ; } } // popping the extra element that // we have pushed as marker q.pop(); } return result; } // Driver program int main() { // Pushing elements into the queue queue< int > q; q.push(4); q.push(5); q.push(-2); q.push(-3); q.push(11); q.push(10); q.push(5); q.push(6); q.push(8); if (pairWiseConsecutive(q)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
Java
import java.util.LinkedList; import java.util.Queue; // Java program to check if successive // pair of numbers in the queue are // consecutive or not public class GFG { // Function to check if elements are // pairwise consecutive in queue static boolean pairWiseConsecutive(Queue<Integer> q) { // Fetching size of queue int n = q.size(); // Pushing extra element to the queue // which acts as marker q.add(Integer.MAX_VALUE); // Result flag boolean result = true ; // If number of elements in the // queue is odd pop elements while // its size is greater than 2. // Else, pop elements while its // size is greater than 1 if (n % 2 != 0 ) { while (n > 2 ) { int x = q.peek(); q.remove(); q.add(x); n--; int y = q.peek(); q.remove(); q.add(y); n--; if (Math.abs(x - y) != 1 ) { result = false ; } } // Popping the last element of queue // and pushing it again. // Also, popping the extra element // that we have pushed as marker q.add(q.peek()); q.remove(); q.remove(); } else { while (n > 1 ) { int x = q.peek(); q.remove(); q.add(x); n--; int y = q.peek(); q.remove(); q.add(y); n--; if (Math.abs(x - y) != 1 ) { result = false ; } } // popping the extra element that // we have pushed as marker q.remove(); } return result; } // Driver program static public void main(String[] args) { // Pushing elements into the queue Queue<Integer> q = new LinkedList<>(); q.add( 4 ); q.add( 5 ); q.add(- 2 ); q.add(- 3 ); q.add( 11 ); q.add( 10 ); q.add( 5 ); q.add( 6 ); q.add( 8 ); if (pairWiseConsecutive(q)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to check if successive # pair of numbers in the queue are # consecutive or not import sys, queue # Function to check if elements are # pairwise consecutive in queue def pairWiseConsecutive(q): # Fetching size of queue n = q.qsize() # Pushing extra element to the # queue which acts as marker q.put( - sys.maxsize); # Result flag result = bool ( True ) # If number of elements in the # queue is odd pop elements while # its size is greater than 2. # Else, pop elements while its # size is greater than 1 if (n % 2 ! = 0 ): while (n > 2 ): x = q.queue[ 0 ] q.get() q.put(x) n - = 1 y = q.queue[ 0 ] q.get() q.put(y) n - = 1 if ( abs (x - y) ! = 1 ): result = bool ( False ) # Popping the last element of queue # and pushing it again. # Also, popping the extra element # that we have pushed as marker q.put(q.queue[ 0 ]) q.get() q.get() else : while (n > 1 ): x = q.queue[ 0 ] q.get() q.put(x) n - = 1 y = q.queue[ 0 ] q.get() q.put(y) n - = 1 if ( abs (x - y) ! = 1 ): result = bool ( False ) # popping the extra element that # we have pushed as marker q.get() return result # Driver code # Pushing elements into the queue q = queue.Queue() q.put( 4 ) q.put( 5 ) q.put( - 2 ) q.put( - 3 ) q.put( 11 ) q.put( 10 ) q.put( 5 ) q.put( 6 ) q.put( 8 ) if ( bool (pairWiseConsecutive(q))): print ( "Yes" ) else : print ( "No" ) # This code is contributed by divyeshrabadiya07 |
C#
// C# program to check if successive // pair of numbers in the queue are // consecutive or not using System; using System.Collections.Generic; class GFG { // Function to check if elements are // pairwise consecutive in queue static Boolean pairWiseConsecutive(Queue< int > q) { // Fetching size of queue int n = q.Count; // Pushing extra element to the queue // which acts as marker q.Enqueue( int .MaxValue); // Result flag Boolean result = true ; // If number of elements in the // queue is odd pop elements while // its size is greater than 2. // Else, pop elements while its // size is greater than 1 if (n % 2 != 0) { while (n > 2) { int x = q.Peek(); q.Dequeue(); q.Enqueue(x); n--; int y = q.Peek(); q.Dequeue(); q.Enqueue(y); n--; if (Math.Abs(x - y) != 1) { result = false ; } } // Popping the last element of queue // and pushing it again. // Also, popping the extra element // that we have pushed as marker q.Enqueue(q.Peek()); q.Dequeue(); q.Dequeue(); } else { while (n > 1) { int x = q.Peek(); q.Dequeue(); q.Enqueue(x); n--; int y = q.Peek(); q.Dequeue(); q.Enqueue(y); n--; if (Math.Abs(x - y) != 1) { result = false ; } } // popping the extra element that // we have pushed as marker q.Dequeue(); } return result; } // Driver Code static public void Main(String[] args) { // Pushing elements into the queue Queue< int > q = new Queue< int >(); q.Enqueue(4); q.Enqueue(5); q.Enqueue(-2); q.Enqueue(-3); q.Enqueue(11); q.Enqueue(10); q.Enqueue(5); q.Enqueue(6); q.Enqueue(8); if (pairWiseConsecutive(q)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by Rajput-Ji |
Javascript
// Javascript program to check if successive // pair of numbers in the queue are // consecutive or not // Function to check if elements are // pairwise consecutive in queue function pairWiseConsecutive(q) { // Fetching size of queue let n = q.length; // Pushing extra element to the queue // which acts as marker q.push(Number.MIN_VALUE); // Result flag let result = true ; // If number of elements in the // queue is odd pop elements while // its size is greater than 2. // Else, pop elements while its // size is greater than 1 if (n % 2 != 0) { while (n > 2) { let x = q[0]; q.shift(); q.push(x); n--; let y = q[0]; q.shift(); q.push(y); n--; if (Math.abs(x - y) != 1) { result = false ; } } // Popping the last element of queue // and pushing it again. // Also, popping the extra element // that we have pushed as marker q.push(q[0]); q.shift(); q.shift(); } else { while (n > 1) { let x = q[0]; q.shift(); q.push(x); n--; let y = q[0]; q.shift(); q.push(y); n--; if (Math.abs(x - y) != 1) { result = false ; } } // popping the extra element that // we have pushed as marker q.shift(); } return result; } // Driver program // Pushing elements into the queue let q = []; q.push(4); q.push(5); q.push(-2); q.push(-3); q.push(11); q.push(10); q.push(5); q.push(6); q.push(8); if (pairWiseConsecutive(q)) console.log( "Yes" ); else console.log( "No" ); // This code is contributed by adityamaharshi21 |
Output
Yes
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(1)